#P18415. Endless Road
Endless Road
Endless Road
一条无限长的直线上放有三枚棋子,初始位置均为整数。两枚或三枚棋子可以位于同一个位置。
每过一秒,从三枚棋子中等概率地选择一枚,将它从坐标 移动到坐标 。每秒只移动所选的那一枚棋子。
对于每个 ,求经过 秒后三枚棋子的最大坐标的期望值。
输入格式
第一行包含三个整数 ,表示三枚棋子的初始坐标,满足
第二行包含一个整数 ,满足 ,表示需要考虑的最大时间。
输出格式
输出 行。第 行输出经过 秒后最大坐标的期望,答案对质数 取模。
具体地,将该期望写为有理数 ,其中 与 互质;输出 ,这里 是模意义下的乘法逆元。
样例 1
输入:
0 0 0
5
输出:
1
332748119
554580198
813384290
110916042
样例 2
输入:
111 222 456
10
输出:
332748574
665496692
457
332748575
665496693
458
332748576
665496694
459
332748577