题目描述

非常に細長いベンチがあります。 このベンチは $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$ で出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $s$

输出格式

$3$ つの有理数 $p,\ q,\ r$ を空白で区切って出力せよ。

题目大意

题目大意

有一个长度为无限的字符串 $S$，刚刚开始时，每个字符都是英文横杠: - 。

现在对它进行更改，操作如下:

随机选字符串其中的一个左右两个字符不是 # 的字符- ,将其修改为 # ,只到没有可以修改的字符。

操作完后，给定整数 $N$ 以及长度为 $N$ 的由 - 和 # 组成字符串 $s$ ,问在 $S$ 中随机取一段长度为 $N$ 的字符串，这个串与 $s$ 相同的概率是多少，让你输出这个概率。

输入格式

输入一共两行，第一行一个正整数 $N$ ，第二行一个长度为 $N$ 的字符串 $s$ 。

输出格式

这个输出比较特殊，由于答案可以表示为 $p + \frac {q}{e} + \frac{r}{e^2}$ （其中 $p,q,r$ 为有理数）。所以输出一共一行3个数，分别是 $p,q,r$ 在模 1000000007 （1e9+7）意义下的数。

1
X

500000004 0 500000003

3
---

0 0 0

5
X--X-

0 0 1

5
X-X-X

500000004 0 833333337

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

0 0 183703705

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

提示

注記

有理数を出力する際は、まずその有理数を分数 $\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 と - からなる。

Sample Explanation 1

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

Sample Explanation 2

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

Sample Explanation 3

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

Sample Explanation 4

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

Sample Explanation 5

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