No.1204 Candy Distribution - FINAL
タグ : / 解いたユーザー数 8
作問者 :
PCTprobability
/ テスター :
hotman78
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$.)
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
Input
$N$ $M$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.
$S$
- $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もしくは右上の雲マークをクリックしてアカウントを作成してください。