問題一覧 > 通常問題

No.1204 お菓子配り-FINAL

レベル : / 実行時間制限 : 1ケース 8.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 4
作問者 : PCTprobabilityPCTprobability / テスター : hotmanwwhotmanww
0 ProblemId : 4812 / 出題時の順位表
問題文最終更新日: 2020-08-28 23:16:53

注意

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

問題文

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

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

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

  • ある$1$ 以上 $N$ 以下の整数 $k$ に対して $k$ 回目の操作 $1$ において選んだ整数が違う場合
  • 写真に写る一番左の子供の番号が一致しない場合
  • 同じ写真撮影タイムで写真を撮影していない場合
ただし答えは非常に大きくなる場合があるので $1000000007$ で割った余りを出力してください。

21:34 問題文を修正しました。 22:25 問題文を修正しました。

入力

$N$ $M$
$S$
ここで$S$とはPCT君の撮った写真を表しています。 oと-から構成されoはその子供がまだお菓子を受け取っていないことを、 -はその子供がもうお菓子を受け取っていることを表します。

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

出力

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

サンプル

サンプル1
入力
3 3
o-o
出力
9

写っている子供としてあり得るものは $(1,2,3)$ のみしかありません。 そして選ばれた数字の列としてあり得るものは例えば $(2,2,3)$ などがあり得ます。

サンプル2
入力
10000 10
oo----oo-o
出力
401451336

$1000000007$ で割った余りを出力してください。

サンプル3
入力
10000 5
--o--
出力
328458186

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。