← 返回题目列表

AtCoder · wtf19_e

E. 自然常数e

中文机器翻译题面 查看原题

分数: 2718 点

问题陈述

有一条很长的长凳。 这条长凳被分成 M 个部分,其中 M 是一个很大的整数。

最初,长凳是空的。 然后, M 个人一个接一个地来到长凳上,并执行以下操作:

  • 我们称一个部分为 舒适的 如果该区段当前无人占用,并且不与任何已占用区段相邻。 如果没有舒适区段,该人会离开长椅。 否则,该人会从舒适区段中随机均匀选择一个,并坐在那里。 (各自的选择是相互独立的)。

毕竟 M 人们执行动作,Snuke 随机均匀选择一个区间的 N 连续区段(从 M-N+1 可能的间隔),并拍一张照片。他的照片可以用一个长度为的字符串来描述 N 组成 X 和 -: i字符串的第一个字符是 X 如果 i-间隔中从左边起第 -节被占据,且 - 否则。注意照片是有方向的。例如, -X--X 和 X--X- 是不同的照片。

照片与给定字符串匹配的概率是多少 s? 这个概率取决于 M。 当 M 趋于无穷大时,你需要计算这个概率的极限。

在这里,我们可以证明极限可以使用三个 理性 号码 p, q, r 和 e = 2.718 \ldots (自然对数的底数)以以下格式唯一表示:

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

你的任务是计算这三个有理数,并按照注释部分的说明打印它们的模。 10^9 + 7,如注释部分所述。

注释

打印有理数时,首先将其写为分数 \frac{y}{x},其中 x, y 是整数并且 x 不能被整除 10^9 + 7 (在问题的约束下,这种表示总是可能的)。 然后,您需要打印唯一的整数 z 之间 0 和 10^9 + 6,包含在内,满足 xz \equiv y \pmod{10^9 + 7}.

约束

  • 1 \leq N \leq 1000
  • |s| = N
  • s 包括 X 和 -.

输入

输入由标准输入按以下格式给出:

N
s

输出

打印三个有理数 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

极限是 \frac{1}{e^2}.


示例输入 4

5
X-X-X

示例输出 4

500000004 0 833333337

极限是 \frac{1}{2} - \frac{13}{6e^2}.


示例输入 5

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

示例输出 5

0 0 183703705

极限是 \frac{7}{675e^2}.


示例输入 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