题目描述

Alice 和 Bob 要玩经典的 Nim 游戏。

游戏开始时有 $K$ 堆石子，第 $i$ 堆中有 $a_i$ 颗石子，其中 $1\le i\le K$。Alice 先手，两人轮流操作。每次操作时，当前玩家选择一堆非空石子，并从中取走至少一颗石子。如果轮到某位玩家时已经没有合法操作，则该玩家失败。

题目要求每个 $a_i$ 都是一个不超过 $L$ 的素数。给定 $K$ 和 $L$，求有多少种有序序列 $(a_1,a_2,\ldots,a_K)$ 满足上述条件，并且在双方都采取最优策略的情况下 Bob 获胜。

答案对 $1\,000\,000\,007$ 取模。

不同石子堆的位置是有区别的：只要存在某个下标 $i$，使得两个初始配置在第 $i$ 堆的石子数不同，就认为它们是不同的配置。例如 $(2,5,7)$ 与 $(2,7,5)$ 是两个不同的配置。

输入格式

一行输入两个整数 $K,L$。

输出格式

输出一个整数，表示满足条件且在双方均采用最优策略时 Bob 获胜的有序初始配置数量，对 $1\,000\,000\,007$ 取模。

数据范围与约定

• $1\le K\le 10^9$；
• $2\le L\le 50000$。

输入输出样例 #1

输入 #1

3 7

输出 #1

6

说明 #1

不超过 $7$ 的素数为 $2,3,5,7$。Bob 获胜的配置恰好是 $(2,5,7)$ 的所有排列，共有 $3!=6$ 种。

输入输出样例 #2

输入 #2

4 13

输出 #2

120

说明 #2

不超过 $13$ 的素数共有 $6$ 个。Bob 获胜的配置分为三类：

• $(p,p,p,p)$，其中 $p\le 13$ 为素数；
• $(p,p,q,q)$ 的任意排列，其中 $p<q\le 13$ 且 $p,q$ 均为素数；
• $(3,5,11,13)$ 的任意排列。

因此答案为 $6+\binom{6}{2}\times 6+4!=6+90+24=120$。

输入输出样例 #3

输入 #3

10 100

输出 #3

294844622