#P18031. Penguin Flicker
Penguin Flicker
Penguin Flicker
一条直线上的格子编号为 ,位置 和 是洞。初始有 只企鹅,分别位于 ,每个格子最多一只企鹅。
反复进行以下随机操作,直到所有企鹅都掉进洞中:
- 在当前剩余企鹅中等概率选一只。
- 以相同概率选择向左或向右。
- 这只企鹅沿选定方向滑行,直到停在该方向另一只企鹅的相邻格子上,或者滑入洞中。滑入洞中的企鹅立即消失。
相邻企鹅可能使一次操作的移动距离为 。移动距离按格子编号之差计算,滑入洞的最后一步也计入距离。
求所有企鹅在整个过程中移动距离之和的期望,答案对 取模。若期望写为最简分数 ,输出 ;题目保证所需逆元存在。
输入格式
第一行一个整数 。每组测试第一行两个整数 ,第二行 个整数 。
输出格式
每组测试输出一行,表示期望值对 取模的结果。
数据范围
,,,。没有额外的 限制。所有输入均为整数。
样例说明
第一组只有一只企鹅。它从位置 向左移动距离为 ,向右移动距离为 ,期望为 。
样例 1
输入:
3
1 8
2
4 7638
7 66 333 888
5 21
2 4 9 15 17
输出:
499122181
308996191
485077673