The programmers from the R2 company love playing 2048. One day, they decided to invent their own simplified version of this game −
2k on a stripe.
Imagine an infinite in one direction stripe, consisting of unit squares (the side of each square is equal to the height of the stripe). Each square can either be empty or contain some number.
Initially, all squares are empty. Then at infinity one of the unit squares number 2 or 4 appears. Then the pla
yer presses a button once, and the appeared number begins to move towards the beginning of the stripe. Let's assume that some number x moves to the beginning of the stripe, then it will stop if:
-
it either gets in the first square of the stripe;
-
or it is in the square that is preceded by a square with number y (y≠x). But if number x at some point of time gets to the square with the same number then both numbers add to each other and result in 2x. The new number 2x continues moving to the beginning of the stripe by the same rules.
After the final stop of the number moving process, the infinity gets a new number 2 or 4 and the process repeats. Read the notes to the test samples to better understand the moving strategy.
I guess you've understood that the game progress fully depends on the order in which numbers 2 and 4 appear. Let's look at some sequence of numbers 2 and 4 in the game. We assume that the sequence is winning if it results in at least one square getting the number greater or equal than 2k.
The goal of the game is to make up a winning sequence of n numbers. But not everything is so simple, some numbers in the sequence are identified beforehand. You are given a sequence consisting of numbers 0, 2, 4. Count how many ways there are to replace each 0 of the sequence with 2 or 4 to get a winning sequence.
Output
Print a single integer − the number of ways to replace zeroes by numbers 2 or 4 to get a winning sequence. As this number can be rather large, print it modulo
1000000007 (109+7).
有一个长为 n 的数列，每一个元素都是 2，4 或是 0。你想要把所有 0替换为 2 或 4，你想知道有多少种替换方法，使得按照 2048 的规则合并后，最大的数超过了 2^k。答案对 10^9+7取模。
2048 合并规则是，依次向一个栈中压入数列中的所有元素。若某次压入的时候，栈顶的元素和即将压入的元素相同，则取出栈顶元素，与即将压入的元素合并为他们二倍的数，然后再将这个数压入栈。若此时还一样，则重复此过程。
Note
Consider the first example. The beginning of the strip will look as follows:
2 → 4 → 8 → 8 2 → 8 4 → 8 4 2 → 16.
To better understand the game, you can see the original game on
http://gabrielecirulli.github.io/2048/. Please note that the game that is described on the strip is slightly different from the original game (when the two numbers add up in the original game, they do not keep moving). Be careful, the game is addictive, there isn't much time for the contest!