/ 
実行時間制限: 4 sec / メモリ制限: 1024 MB
Score : 2718 points
Problem Statement
There is a very long bench. The bench is divided into M sections, where M is a very large integer.
Initially, the bench is vacant. Then, M people come to the bench one by one, and perform the following action:
- We call a section comfortable if the section is currently unoccupied and is not adjacent to any occupied sections. If there is no comfortable section, the person leaves the bench. Otherwise, the person chooses one of comfortable sections uniformly at random, and sits there. (The choices are independent from each other).
After all M people perform actions, Snuke chooses an interval of N consecutive sections uniformly at random (from M-N+1 possible intervals), and takes a photo.
His photo can be described by a string of length N consisting of X and -: the i-th character of the string is X if the i-th section from the left in the interval is occupied, and - otherwise.
Note that the photo is directed.
For example, -X--X and X--X- are different photos.
What is the probability that the photo matches a given string s? This probability depends on M. You need to compute the limit of this probability when M goes infinity.
Here, we can prove that the limit can be uniquely written in the following format using three rational numbers p, q, r and e = 2.718 \ldots (the base of natural logarithm):
p + \frac{q}{e} + \frac{r}{e^2}
Your task is to compute these three rational numbers, and print them modulo 10^9 + 7, as described in Notes section.
Notes
When you print a rational number, first write it as a fraction \frac{y}{x}, where x, y are integers and x is not divisible by 10^9 + 7 (under the constraints of the problem, such representation is always possible). Then, you need to print the only integer z between 0 and 10^9 + 6, inclusive, that satisfies xz \equiv y \pmod{10^9 + 7}.
Constraints
- 1 \leq N \leq 1000
- |s| = N
- s consists of
Xand-.
Input
Input is given from Standard Input in the following format:
N s
Output
Print three rational numbers p, q, r, separated by spaces.
Sample Input 1
1 X
Sample Output 1
500000004 0 500000003
The probability that a randomly chosen section is occupied converge to \frac{1}{2} - \frac{1}{2e^2}.
Sample Input 2
3 ---
Sample Output 2
0 0 0
After the actions, no three consecutive unoccupied sections can be left.
Sample Input 3
5 X--X-
Sample Output 3
0 0 1
The limit is \frac{1}{e^2}.
Sample Input 4
5 X-X-X
Sample Output 4
500000004 0 833333337
The limit is \frac{1}{2} - \frac{13}{6e^2}.
Sample Input 5
20 -X--X--X-X--X--X-X-X
Sample Output 5
0 0 183703705
The limit is \frac{7}{675e^2}.
Sample Input 6
100 X-X-X-X-X-X-X-X-X-X--X-X-X-X-X-X-X-X-X-X-X-X-X-X-X--X--X-X-X-X--X--X-X-X--X-X-X--X-X--X--X-X--X-X-X-
Sample Output 6
0 0 435664291
配点 : 2718 点
問題文
非常に細長いベンチがあります。 このベンチは M 個の区画に分かれています。ここで、M は非常に大きい整数です。
はじめ、ベンチには誰も座っていません。 このベンチに M 人の人たちが一人ずつ訪れ、以下の行動を行います。
- まだ人が座っておらず、人が座っている区画と隣接もしていないような区画を 快適 であると呼ぶことにする。 快適な区画が存在しなければ、ベンチから立ち去る。 そうでなければ、快適な区画の一つを一様ランダムに選んでそこに座る (人々の座る区画の選択は互いに独立である)。
M 人全員が上記の行動を取ったあと、すぬけ君は N 個の連続する区画からなる区間を (M-N+1 個の候補から) 一様ランダムに選び、その区間の写真を撮ります。
この写真は、X と - からなる長さ N の次のような文字列により表現できます: i 文字目は、区間の左から i 番目の区画に人が座っていれば X、そうでなければ - であるような文字列。
なお、写真の左右は区別されます。
例えば、-X--X と X--X- は異なる写真です。
撮った写真が与えられる文字列 s に一致する確率はいくつでしょうか？ この確率は M に依存しますが、M が限りなく大きくなるときのこの確率の極限を求めてください。
ここで、この極限は 3 つの有理数 p, q, r と e = 2.718 \ldots (自然対数の底) を用いて以下の形式で一意に表せることが証明できます。
p + \frac{q}{e} + \frac{r}{e^2}
これら 3 つの有理数を求め、それらを注記で述べるように mod 10^9 + 7 で出力してください。
注記
有理数を出力する際は、まずその有理数を分数 \frac{y}{x} として表してください。ここで、x, y は整数であり、x は 10^9 + 7 で割り切れてはなりません (この問題の制約下で、そのような表現は必ず可能です)。そして、xz \equiv y \pmod{10^9 + 7} を満たすような 0 以上 10^9 + 6 以下の唯一の整数 z を出力してください。
制約
- 1 \leq N \leq 1000
- |s| = N
- s は
Xと-からなる。
入力
入力は以下の形式で標準入力から与えられる。
N s
出力
3 つの有理数 p, q, r を空白で区切って出力せよ。
入力例 1
1 X
出力例 1
500000004 0 500000003
ランダムに選ばれた区画に人が座っている確率は \frac{1}{2} - \frac{1}{2e^2} に収束します。
入力例 2
3 ---
出力例 2
0 0 0
人々の行動のあと、人が座っていない区画が 3 つ連続して残ることはありません。
入力例 3
5 X--X-
出力例 3
0 0 1
極限は \frac{1}{e^2} です。
入力例 4
5 X-X-X
出力例 4
500000004 0 833333337
極限は \frac{1}{2} - \frac{13}{6e^2} です。
入力例 5
20 -X--X--X-X--X--X-X-X
出力例 5
0 0 183703705
極限は \frac{7}{675e^2} です。
入力例 6
100 X-X-X-X-X-X-X-X-X-X--X-X-X-X-X-X-X-X-X-X-X-X-X-X-X--X--X-X-X-X--X--X-X-X--X-X-X--X-X--X--X-X--X-X-X-
出力例 6
0 0 435664291