CF273E.Dima and Game

Dima 和 Anya 喜欢玩各种各样的游戏。现在 Dima 想出了一个新游戏，他想和 Anya 一起玩。

Dima 在一张纸上写下 $n$ 个整数对 $(l_i, r_i)\ (1 \leq l_i < r_i \leq p)$。然后两位玩家轮流操作。在自己回合时，玩家可以进行以下操作：

1. 选择第 $i$ 个数对 $(1 \leq i \leq n)$，要求 $r_i - l_i > 2$；
2. 用数对 $\left(l_i + \left\lfloor \dfrac{r_i - l_i}{3} \right\rfloor , l_i +2 \cdot \left\lfloor \dfrac{r_i - l_i}{3} \right\rfloor \right)$ 或$\left(l_i, r_i -\left\lfloor \dfrac{r_i - l_i}{3} \right\rfloor \right)$ 替换原来的第 $i$ 个数对。符号 $⌊x⌋$ 表示向下取整。

无法进行操作的玩家判负。

当然，Dima 想让先手的 Anya 获胜。因此，Dima 需要选择满足条件的 $n$ 个数对 $(l_i, r_i)\ (1 \leq l_i < r_i \leq p)$，使得在两人都采取最优策略的情况下，先手必胜。请计算 Dima 可以选择的方案数。请将答案对 $1000000007\ (10^9+7)$ 取模后输出。

如果两组数对的有序排列不同，则认为这两种方案不同。

第一行包含两个整数 $n$、$p\ (1 \leq n \leq 1000, 1 \leq p \leq 10^9)$，两数之间用空格分隔。

输出一行，表示满足条件的方案数对 $1000000007\ (10^9+7)$ 取模后的结果。

由 ChatGPT 5 翻译