← 返回题目列表

Codeforces · 273/E

E. 迪玛和游戏

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

Dima 和 Anya 喜欢玩不同的游戏。现在迪马想出了一款新游戏,他想和安雅一起玩。

Dima 在一张纸上写下 n 对整数 (li, ri) (1 ≤ li < ri ≤ p)。然后玩家轮流进行。轮到玩家可以执行以下操作:

1.选择i对的个数(1 ≤ i ≤ n),使得ri - li > 2;
2. 将编号 i 替换为对 $$( l _ { i } + \left\lfloor \frac { r _ { i } - l _ { i } } { 3 } \right\rfloor, l _ { i } + 2 \cdot \left\lfloor \frac { r _ { i } - l _ { i } } { 3 } \right\rfloor )$$ 或成对 $$( l _ { i }, r _ { i } - \left\lfloor \frac { r _ { i } - l _ { i } } { 3 } \right\rfloor )$$。符号 ⌊x⌋ 表示向下舍入到最接近的整数。

无法移动的玩家失败。

迪玛当然希望先行动的安雅获胜。这就是为什么 Dima 应该写出这样 n 对整数 (li, ri) (1 ≤ li < ri ≤ p),如果两个玩家都发挥最佳,则第一个获胜。数一数迪马有多少种方法可以做到这一点。打印答案除以数字 1000000007 (109 + 7) 后的余数。

如果写入对的有序序列不同,则两种方式被认为是不同的。

输入

第一行包含两个整数 n, p (1 ≤ n ≤ 1000, 1 ≤ p ≤ 109)。数字之间用一个空格分隔。

输出

在一行中打印问题答案除以数字 1000000007 (109 + 7) 后的余数。

示例

输入 #1

2 2

输出 #1

0

输入 #2

4 4

输出 #2

520

输入 #3

100 1000

输出 #3

269568947