在火星上，尽管大气非常稀薄，但风力有时会出人意料地强劲。这种效应在赤道附近狭窄而深邃的峡谷中会变得更加强烈。其中一条峡谷的底部非常平坦，由于其陡峭的岩壁能提供部分宇宙辐射屏蔽，因此被用作运输通道。随着时间的推移，沙子在峡谷中堆积，被风吹成了巨大的沙丘，阻碍了交通。这些沙丘在峡谷底部形成了一长串沙丘序列。

沙丘的排列并不稳定。肆虐的沙尘暴经常将沙丘重塑成不同的序列。风暴中沙团的剧烈运动产生了一种怪异的声音，沙丘也因此被称为“风暴中的尖叫者”（Screamers in the storm）。

对沙丘的详细测量显示，相邻沙丘的高度（以火星米为单位）始终是一个较小的正整数。此外，可能是由于峡谷中的风干扰效应，相邻两个沙丘的高度总是不同的，除非它们都为 1。事实上，相邻两个沙丘的高度总是互质的，也就是说，它们没有大于 1 的公因子。

为了模拟沙丘的行为，需要确定该序列中所有可能的沙丘配置数量。

输入格式

输入包含一行，包含两个整数 $K$ 和 $N$（$1 \le K \le 66$，$1 \le N \le 10^{18}$），分别表示沙丘的最大可能高度和沙丘序列中沙丘的数量。

输出格式

输出不同沙丘序列的数量。将结果对 $10^9 + 7$ 取模。

样例

输入 1

3 4

输出 1

41

输入 2

2 4

输出 2

8

输入 3

42 75097099101114

输出 3

673977658