Problem Statement

Fill each of $x,y,z,w$ in the table above with one of $0,1$, and define $S_{x+2y+4z+8w}$ as the operation that applies the table above to each bit of non-negative integers $a,b$. For example, $S_6$ gives $1$ when the bits of $a,b$ differ and $0$ when they are the same, so it is XOR.

You are given a positive integer $N$ and a string $K$ of $8$ characters, each of which is o or -. For each non-negative integer between $0$ and $7$ inclusive such that $K_{i+1}$ is o, call it $i$ and take the following value; output the sum of these values modulo $1000000007$.

The number of triples $(P,Q,R)$ of non-negative integers that are at least $0$ and less than $2^N$ and satisfy $((P$ $S_i$ $Q )-R)×((P$ $S_{15-i}$ $Q) -R) \le 0$. Here, compute each operation with leading zeros inserted so that its result has exactly $N$ digits. (Added at 21:45)

Input

$N$
$K$

• $N$ is an integer.
• $K$ is a string whose characters are all o or -.
• $0 \le N \le 10^{18}$
• $|K|=8$

Output

Output the value described in the problem statement.

Sample

3
-o------

368

4736175978463
o--o-oo-

942654651