分数: 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