#2098. Claris的剑

Claris的剑

Description

Claris想要铸一把剑,这把剑必须符合他的审美,具体来说,我们可以把这把剑的不同地方的宽度看成一个序列,这个序列要满足以下条件: 1.每个元素都是正整数(你的宽度不可能是负数吧) 2.每个元素不能超过M,太宽了如果比Claris身高还高怎么办(你可以认为Claris的身高就是M) 3.相邻两个元素的差的绝对值必须是1(如果是0,则这个地方不是锯齿,杀伤力不够,如果太大,又太丑了) 4.第一个元素的值必须是1(剑尖必须是最窄的地方) 他想知道有多少把长度不超过N(即宽度的序列长度不超过N)的合法的本质不同的剑。 我们认为两把剑本质不同,当且仅当存在至少一个宽度,在两把剑的宽度序列里面出现次数不一样。 比如{1,2,3}和{1,3,2}是本质相同的 {1,2,3}和{1,2,1}则是本质不同的

Format

Input

只有两个整数,表示N,M (数据保证N,M2000000N,M≤2000000)

Output

只有一个整数,表示答案对109**+**7109+7取模的结果

Samples

5 3
9

Limitation

样例解释

所有本质不同的合法的剑有如下:

{1}

{1,2}

{1,2,3}

{1,2,1}

{1,2,3,2}

{1,2,1,2}

{1,2,3,2,3}

{1,2,3,2,1}

{1,2,1,2,1}