問題文

上の表の $x,y,z,w$ に $0,1$ のどちらかを入れ、非負整数 $a,b$ の各bitに対して上の表を使うという演算を $S_{x+2y+4z+8w}$ と定義します。 例えば、$S_6$ は $a,b$ のbitが違う時は $1$、同じときは $0$ なのでXORのことです。

正整数 $N$ と全ての文字がoか-である $8$ 文字の文字列 $K$ が与えられます。 $0$ 以上 $7$ 以下かつ $K_{i+1}$ が o である非負整数 $i$ に対して以下の値を合計を $1000000007$ で割った余りを出力してください。

$0$ 以上 $2^N$ 未満の非負整数の組 $(P,Q,R)$ であって、$((P$ $S_i$ $Q)-R)\times ((P$ $S_{15-i}$ $Q)-R)\le 0$ を満たすものの数。ただし、それぞれの演算の計算結果はちょうど $N$ 桁となるようleading-zeroをいれて計算してください。(21:45 追記)

入力

$N$
$K$

• $N$ は整数である。
• $K$ は全ての文字がoか-の文字列である。
• $0\le N\le {10}^{18}$
• $|K|=8$

出力

問題文に書かれている値を出力してください。

サンプル

3
-o------

368

4736175978463
o--o-oo-

942654651