Score : 2718 points
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:
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.
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}.
X
and -
.Input is given from Standard Input in the following format:
N s
Print three rational numbers p, q, r, separated by spaces.
1 X
500000004 0 500000003
The probability that a randomly chosen section is occupied converge to \frac{1}{2} - \frac{1}{2e^2}.
3 ---
0 0 0
After the actions, no three consecutive unoccupied sections can be left.
5 X--X-
0 0 1
The limit is \frac{1}{e^2}.
5 X-X-X
500000004 0 833333337
The limit is \frac{1}{2} - \frac{13}{6e^2}.
20 -X--X--X-X--X--X-X-X
0 0 183703705
The limit is \frac{7}{675e^2}.
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-
0 0 435664291