ABC242 E - (∀x∀) (500)
回文なのでXは前半分だけを考える
後半分は自動的に決まる
前半分が完全にSと同じになるXについて$ X \le Sを満たしているか確認しておく
$ dp[i][j][k] で$ i文字目まで見てその文字が$ jで$ Sより真に小さいかどうかの場合の数
0文字目については$ dp[0][S_0][0] = 1 , $ dp[0][i(i \lt S_0)][1] = 1
$ i文字目については
$ dp[i][S_i][0] = dp[i-1][S_{i-1}][0] , $ dp[i][j (j \lt S_i)][1] += dp[i-1][S_{i-1}][0] , $ dp[i][j][1] += dp[i-1][k][1]
最後に$ m = \frac{n+1}{2} として$ \sum_i^{26}dp[m-1][i][1] が答え
前半分が完全にSと同じになるXについて$ X \le S を満たしているなら$ dp[m-1][S_{m-1}][0] も足す