题目描述

题目大意

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

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

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

操作完后，给定整数 $N$ 以及长度为 $N$ 的由 - 和 X 组成字符串 $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

输入 #1

1
X

输出 #1

500000004 0 500000003

输入输出样例 #2

输入 #2

3
---

输出 #2

0 0 0

输入输出样例 #3

输入 #3

5
X--X-

输出 #3

0 0 1

输入输出样例 #4

输入 #4

5
X-X-X

输出 #4

500000004 0 833333337

输入输出样例 #5

输入 #5

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

输出 #5

0 0 183703705

输入输出样例 #6

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

说明/提示

注記

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