#1722. EntropyIncreaser 与 Minecraft

EntropyIncreaser 与 Minecraft

题目描述

EntropyIncreaser 是组合计数大师。

EntropyIncreaser 很喜欢玩麦块。当然,EntropyIncreaser 拥有非同常人的超能力,他玩的是魔改版的 nn 维麦块,换成数学语言也就是 Zn\mathbb Z^n 空间。他现在手里有一个特制的炸药方块:若将它放在 (x1,x2,,xn)(x_1,x_2,\dots,x_n)(注意 xix_i 可能为负数)处,它将拥有 i=1nxi\displaystyle \sum_{i=1}^{n}\left|x_{i}\right| 的威力值。EntropyIncreaser 只是想看看这种特制炸药的爆炸场面,他并不希望对其他东西造成太大的损害,所以这个炸药方块的威力值必须 p\leqslant p

EntropyIncreaser 想请你告诉他,一共有多少不同的位置放置炸药,使其满足他的要求。答案对 109+710^9+7 取模。

EntropyIncreaser 想了一秒就知道了答案。但他决定还是考考你。

输入格式

一行两个数 n,pn,p,含义见题目描述。

输出格式

一行一个整数表示答案。

样例

3 5
231

数据范围与提示

对于 10%10\% 的数据,n,p5n,p\leqslant 5

对于 50%50\% 的数据,n,p1000n,p \leqslant 1000

对于 100%100\% 的数据,n,p106n,p \leqslant 10^6

Bonus:n106,p109n \leqslant 10^6, p \leqslant 10^9