問題一覧 > 通常問題

No.1204 Candy Distribution - FINAL

レベル : / AI推定難易度 : 2950 / 実行時間制限 : 1ケース 8.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 8
作問者 : PCTprobability / テスター : hotman78
お気に入りにしたユーザー ProblemId : 4812 / 自分の提出
問題文最終更新日: 2020-08-28 23:16:53
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 263 (順位表) の他の問題:

Note

The time limit for this problem is set rather long. Please be careful.

Problem Statement

There are $N$ children, numbered from $1$ to $N$. The children are lined up so that their numbers are $1,2,\dots ,N$ from the left. PCT-kun then keeps performing the following operations until there are no children without candy.

  • Operation $0$: Hold a photo time. (However, a photo can be taken only $1$ time.)
  • Operation $1$: Randomly choose an integer from $1$ to $N$ and give candy to the child with the chosen number.
  • Operation $2$: If a child has $2$ or more candies, repeatedly have that child pass just $1$ candy (keeping the other $1$ candy) to the child whose number is $1$ greater. (Here, child number $N+1$ means child number $1$.)
The operations are repeated in the order $0,1,2,0,1,2,....,0,1,2,0$. The photo is taken so that exactly $M$ children appear in it. However, a photo that straddles children $N,1$, such as $N-1,N,1,2$, cannot be taken.

Find the number of possible ways of performing the operations. Two ways of performing the operations are considered different if any of the following conditions holds.

  • For some integer $k$ between $1$ and $N$ inclusive, the integers chosen in the $k$-th operation $1$ differ
  • The numbers of the leftmost child appearing in the photo do not match
  • The photos were not taken during the same photo time
Since the answer can be very large, output it modulo $1000000007$.

21:34 The problem statement was corrected. 22:25 The problem statement was corrected.

Input

$N$ $M$
$S$
Here, $S$ represents the photo taken by PCT-kun. It consists of o and -, where o means that the child has not yet received candy, and - means that the child has already received candy.

  • $1 \le N \le 100000=10^5$
  • $1 \le M \le min(N,100=10^2$)
  • $|S|=M$
  • $S$ consists of o and -.

Output

Output the number asked for in the problem statement modulo $1000000007$, followed by a newline.

Sample

Sample 1
Input
3 3
o-o
Output
9

The only possibility for the children in the photo is $(1,2,3)$. A possible sequence of chosen numbers is, for example, $(2,2,3)$.

Sample 2
Input
10000 10
oo----oo-o
Output
401451336

Output the answer modulo $1000000007$.

Sample 3
Input
10000 5
--o--
Output
328458186

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