AT_wtf19_e e

[problemUrl]: https://atcoder.jp/contests/wtf19/tasks/wtf19_e 非常に細長いベンチがあります。 このベンチは $ 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/A

N/A

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