Contest Duration: - (local time) (240 minutes) Back to Home
E - e /

Time Limit: 4 sec / Memory Limit: 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 X and -.

### 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


### 問題文

はじめ、ベンチには誰も座っていません。 このベンチに M 人の人たちが一人ずつ訪れ、以下の行動を行います。

• まだ人が座っておらず、人が座っている区画と隣接もしていないような区画を 快適 であると呼ぶことにする。 快適な区画が存在しなければ、ベンチから立ち去る。 そうでなければ、快適な区画の一つを一様ランダムに選んでそこに座る (人々の座る区画の選択は互いに独立である)。

M 人全員が上記の行動を取ったあと、すぬけ君は N 個の連続する区画からなる区間を (M-N+1 個の候補から) 一様ランダムに選び、その区間の写真を撮ります。 この写真は、X- からなる長さ N の次のような文字列により表現できます: i 文字目は、区間の左から i 番目の区画に人が座っていれば X、そうでなければ - であるような文字列。 なお、写真の左右は区別されます。 例えば、-X--XX--X- は異なる写真です。

ここで、この極限は 3 つの有理p, q, re = 2.718 \ldots (自然対数の底) を用いて以下の形式で一意に表せることが証明できます。

p + \frac{q}{e} + \frac{r}{e^2}

これら 3 つの有理数を求め、それらを注記で述べるように mod 10^9 + 7 で出力してください。

### 制約

• 1 \leq N \leq 1000
• |s| = N
• sX- からなる。

### 入力

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

5
X--X-


### 出力例 3

0 0 1


### 入力例 4

5
X-X-X


### 出力例 4

500000004 0 833333337


### 入力例 5

20
-X--X--X-X--X--X-X-X


### 出力例 5

0 0 183703705


### 入力例 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