题目描述

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}则是本质不同的

输入格式

只有两个整数，表示N,M (数据保证$N,M \leq 2000000$)

输出格式

只有一个整数，表示答案对$10^9+7$取模的结果

5 3

9

提示

样例解释 所有本质不同的合法的剑有如下： {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}

题目来源

By lyzy