Derrick is cultivating a garden of Orz Trees, planted in a line. Derrick's garden can be represented by a sequence of positive integers , with representing the height of the Orz Tree in the line.
Derrick wants to grow more Orz Trees in his garden, but he ran out of Orz Seedlings to plant. Fortunately, Orz Trees aren't like other trees. When an Orz Tree with even height is cut down, two Orz Trees with exactly half the height of the tree appear side-by-side in its place! Note that it is impossible to cut down an Orz Tree with odd height.
Derrick wants to know, after cutting down or more Orz Trees with even height, how many distinct gardens can he make? Two gardens are distinct if and only if the sequences representing the heights of the trees in the gardens are distinct. Since the answer may be very large, output it modulo .
Subtask 1 [50%]
Subtask 2 [50%]
No additional constraints.
The first line contains an integer , the initial number of Orz Trees in Derrick's garden.
The second line contains integers , the height of the tree in Derrick's garden.
Output a single integer, the number of distinct gardens Derrick can make by cutting down or more Orz Trees with even height, modulo .
Sample Input 1
3 6 5 2
Sample Output 1
Explanation for Sample Output 1
Derrick can choose to cut down the first and/or last Orz Trees, or to cut down nothing. The possible gardens he can make are , , , and .
Sample Input 2
Sample Output 2
Explanation for Sample Output 2
If Derrick cuts down the tree of height , his garden becomes . From there, he can choose to cut down either, both, or neither of the trees of height . So, the possible gardens he can make are , , , , and .