2454: 回文拆分

大家都知道回文串吧～简单地说就是左右对称的一个串，比如abcba,werrew。

小s对回文串的研究已经够深刻了，现在她转而研究其他方面的回文，比如，数的回文拆分。对于自然数的拆分，就是把一自然数用若干个整数之和表示。比如15=1+2+3+4+5=1+2+1+7+1+2+1。那么怎样的拆分才算是回文的呢？我们用从归纳的角度来定义数的回文拆分。首先一个数A=A 是一个回文拆分。其次，一个自然数N=A+A 或是N=A+x+A，其中A 是一个回文拆分，x 是任意一个自然数，这两种也是回文拆分。

举个例子，7 的所有回文拆分有7,1+5+1,2+3+2,1+1+3+1+1,3+1+3,1+1+1+1+1+1+1。现在小s想知道，一个正整数N 的回文拆分到底有多少种。由于这个数字可能很大，小s只需要你告诉她答案mod 1,000,000,007 的值。

一行，一个正整数N

一行，一个整数M，为N 的回文拆分数mod 1,000,000,007 的值

4

4