#P18591. Dice Game
Dice Game
Dice Game
有一枚公平的 面骰子,骰面上的数字依次为 。每次掷骰得到各数字的概率均为 ,两次结果相互独立。
游戏首先掷一次骰子,得到 。看到 后,可以选择以下一种操作:
- 立即结束,得分为 ;
- 再掷一次,得到 后结束,得分为 。
其中 是按位异或。若选择第二种操作,不能在看到 后撤销或改选第一种操作。
双方合作使最终得分的数学期望尽可能大。对每个给定的 ,求采用最优决策时的期望得分,并对 取模。
输入格式
第一行给出整数 ,表示询问数。
接下来 行,每行一个整数 。
数据范围为 、。
输出格式
对每个 输出一行一个整数,为对应期望在模 意义下的值。
具体地,将期望写为最简分数 。数据保证 不是 的倍数,输出 ,取值为 。
样例输入 1
4
1
2
3
4
样例输出 1
0
249561089
776412276
2