Lee couldn't sleep lately, because he had nightmares. In one of his nightmares (which was about an unbalanced global round), he decided to fight back and propose a problem below (which you should solve) to balance the round, hopefully setting him free from the nightmares.

A non-empty array $b_1, b_2, \ldots, b_m$ is called good, if there exist $m$ integer sequences which satisfy the following properties:

The $i$-th sequence consists of $b_i$ consecutive integers (for example if $b_i = 3$ then the $i$-th sequence can be $(-1, 0, 1)$ or $(-5, -4, -3)$ but not $(0, -1, 1)$ or $(1, 2, 3, 4)$).

Assuming the sum of integers in the $i$-th sequence is $sum_i$, we want $sum_1 + sum_2 + \ldots + sum_m$ to be equal to $0$.

You are given an array $a_1, a_2, \ldots, a_n$. It has $2^n - 1$ nonempty subsequences. Find how many of them are good.

As this number can be very large, output it modulo $10^9 + 7$.

An array $c$ is a subsequence of an array $d$ if $c$ can be obtained from $d$ by deletion of several (possibly, zero or all) elements.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the size of array $a$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — elements of the array.


-----Output-----

Print a single integer — the number of nonempty good subsequences of $a$, modulo $10^9 + 7$.


-----Examples-----

Input
4
2 2 4 7
Output
10
Input
10
12391240 103904 1000000000 4142834 12039 142035823 1032840 49932183 230194823 984293123
Output
996


-----Note-----

For the first test, two examples of good subsequences are $[2, 7]$ and $[2, 2, 4, 7]$:

For $b = [2, 7]$ we can use $(-3, -4)$ as the first sequence and $(-2, -1, \ldots, 4)$ as the second. Note that subsequence $[2, 7]$ appears twice in $[2, 2, 4, 7]$, so we have to count it twice.

Green circles denote $(-3, -4)$ and orange squares denote $(-2, -1, \ldots, 4)$.

For $b = [2, 2, 4, 7]$ the following sequences would satisfy the properties: $(-1, 0)$, $(-3, -2)$, $(0, 1, 2, 3)$ and $(-3, -2, \ldots, 3)$

Difficulty: HARD
Tags: Number theory

Combinatorics

Dynamic programming

Mathematics
Skill types: Dynamic programming

Starter code:

Solutions:
import sys
mod = 10 ** 9 + 7
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
i = 0
cnt = {}
for x in arr:
	lb = x & -x
	cnt[lb] = cnt.get(lb, 0) + 1
c2 = [cnt.get(1 << i, 0) for i in range(32)]
while c2[-1] == 0:
	c2.pop()
x = 1
y = n - c2[0]
for i in c2[1:]:
	y -= i
	if i > 0:
		x = (x + pow(2, i - 1, mod) * pow(2, y, mod)) % mod
print((pow(2, n, mod) - x) % mod)


M = 10 ** 9 + 7
r = pow(2, int(input()), M) - 1
a = [0] * 99
for i in input().split():
	a[bin(int(i))[::-1].index('1')] += 1
print((r - sum((pow(2, sum(a[i:]) - 1, M) for i in range(1, 30) if a[i]))) % M)


MD = 10 ** 9 + 7

def pow(x, y):
	if y == 0:
		return 1
	m = pow(x, y // 2)
	ans = m * m % MD
	return ans * x % MD if y & 1 else ans
n = int(input())
bit = [0] * 31
for num in map(int, input().split()):
	bit[bin(num)[::-1].index('1')] += 1
ans = pow(2, n) - 1
for i in range(1, 31):
	if bit[i]:
		ans = (ans - pow(2, sum(bit[i:]) - 1)) % MD
print(ans)


r = 2 ** int(input()) - 1
a = [0] * 99
for i in input().split():
	a[bin(int(i))[::-1].index('1')] += 1
print((r - sum(set((2 ** sum(a[i:]) for i in range(1, 30)))) // 2) % (10 ** 9 + 7))


import sys
import math
inpu = sys.stdin.readline
prin = sys.stdout.write

def nu2(n):
	i = 0
	while n % 2 == 0:
		i += 1
		n //= 2
	return i
n = int(inpu())
a = list(map(int, inpu().split()))
even = [guy for guy in a if guy % 2 == 0]
two = [nu2(guy) for guy in even]
two.sort()
counts = [0] * two[-1]
for guy in two:
	counts[guy - 1] += 1
bad = 0
m = 1000000007
for i in range(len(counts)):
	if counts[i] > 0:
		bad += pow(2, sum(counts[i:]) - 1, m)
print((pow(2, n, m) - bad - 1) % m)


n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
c = [0] * 30
for i in a:
	z = 0
	while i & 1 == 0:
		i >>= 1
		z += 1
	c[z] += 1
w = n - c[0]
ans = 2 ** n - 1
for i in range(1, 30):
	if c[i]:
		w -= c[i]
		ans = (ans - pow(2, c[i] - 1, mod) * pow(2, w, mod)) % mod
print((ans + mod) % mod)