https://codeforces.com/contest/1673/problem/C
問題特有の考察はできたけどDPが解けなかった。 分割数って有名問題らしいけど難しい。
制約から40000以下の回文数はすくなそう（M種類）となって、dp[N][M] = 和がNのとき最後に使ったのがM番目の回文数のときの場合の数としてDPすれば行けるかと思った。この場合遷移にもかかって、全体で
になって間に合わなかった。
この問題は分割数として有名問題みたい。
とはいえ難しい。
結論はdp[N][M] を和がNのときM番目以下の回文数を使う時の場合の数として、
dp[N][M] = dp[N-d][M] + dp[N][M-1]
（d=M番目の回文数）
となる。
なぜこれでうまくいくのか。 dp[i][j]を更新する時を考える。
j番目の回文数=d 以下をつかって和がiになる場合の数を求めたい。
dを使わない場合dp[i][j-1]なのは明らかで、これが式の右側。
（j-1番目以下の数をつかっているのでdは使用されていない）
dを少なくとも1回使う場合、d以下の回文数をつかって和が(i-d)になる場合の数になって、これが式の左側。
dp[i-d][j]はdを使っているかいないかを問わないことがポイント。
dp[i-d][j]がdを使っていなくても、i=i-d+d としてdを少なくとも一回は絶対つかう場合の数を考えていることに注意。
dを含まない場合と、dを少なくとも1つ使用する場合で全パターン網羅できることもポイント。
dpの初期化はdp[0][j]=1
j番目以下の回文数を使って、和が0のときの場合の数を1とする
以上を実装してAC。
