注意

この問題はTLが長めに設定されています。注意してください。

問題文

$N$ 人の子供がいて、$1$ から $N$ の番号がついています。 子供達は左から番号が $1,2,\dots ,N$ となるように並んでいます。 この時PCT君は次の操作をお菓子を持っていない子供がいなくなるまで続けます。

• 操作 $0$ ：写真撮影タイムを設ける。(ただし写真を撮れるのは $1$ 回のみです。)
• 操作 $1$ ：ランダムに $1$ から $N$ の整数を選び選んだ番号の子供のお菓子を渡す。
• 操作 $2$ ：もしお菓子を $2$ 個以上持っていたらお菓子を $1$ 個だけ(もう $1$ 個は持ったまま)番号が $1$ 大きい子供にお菓子を渡すを繰り返す。(ただし $N+1$ 番の子供とは $1$ 番の子供とします。)

あり得る操作の場合の数を答えなさい。 操作が違うとは以下の条件の内いずれかを満たす時とします。

• ある$1$ 以上 $N$ 以下の整数 $k$ に対して $k$ 回目の操作 $1$ において選んだ整数が違う場合
• 写真に写る一番左の子供の番号が一致しない場合
• 同じ写真撮影タイムで写真を撮影していない場合

入力

$N$ $M$
$S$

• $1\le N\le 100000={10}^5$
• $1\le M\le min(N,100={10}^2$)
• $|S|=M$
• $S$はoか-で構成される。

出力

問題文で問われているものの数を $1000000007$ で割った余りを出力し最後に改行してください。

サンプル

3 3
o-o

9

10000 10
oo----oo-o

401451336

10000 5
--o--

328458186