题目描述

薯条哥定义一个数组是好数组，当且仅当所有奇数出现了奇数次，所有偶数出现了偶数次。现在薯条哥拿到了一个数组，他希望取一个该数组的非空子序列(可以不连续)，使得子序列是好数组。你能帮薯条哥求出子序列的方案数吗?由于答案过大，请对$10^9+ 7$取模。

输入描述

第一行输入一个正整数$n(1\le n\le 10^5)$，代表数组的大小

第二行输入$n$个正整数$a_i(1\le a_i\le 10^9)$，代表数组的元素

输出描述

一个整数，代表是“好数组”的子序列数量，对$10^9+7$取模的值。

样例

输入

4
1 2 3 2

输出

7