配点 : $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
X

500000004 0 500000003

ランダムに選ばれた区画に人が座っている確率は $\frac{1}{2} - \frac{1}{2e^2}$ に収束します。

3
---

0 0 0

人々の行動のあと、人が座っていない区画が $3$ つ連続して残ることはありません。

5
X--X-

0 0 1

極限は $\frac{1}{e^2}$ です。

5
X-X-X

500000004 0 833333337

極限は $\frac{1}{2} - \frac{13}{6e^2}$ です。

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

0 0 183703705

極限は $\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