辞書順なので，先頭から決めていくことを考える． 回文なので，真ん中まで決めれば残りは自動で決まる．
桁DPのときに近い． 先頭から文字列を決めていって，既に真に(辞書順で)小さいことが確定しているか否か \(\in Bool\) を保持しながら遷移する． 次に決めようとしているのを \(i\) 文字目とする．
- 既に真に小さいことが確定しているのなら，次の文字は 26文字から自由に決められる．
- そうでないときは，次の文字が
- \(s[i]\) と同じときは，まだ小さいか未確定の状態が続く．
- \(s[i]\) 未満のときは，真に小さいことが確定する．
- \(s[i]\) より真に大きいものは選べない．
真ん中まで来たとき，すでに真に小さいと確定している部分はそのまま答えに使える． まだ確定してないとき，本当に回文になっているか個別に確かめる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll t; cin >> t;
rep(ti,t){
ll n; cin >> n;
string s; cin >> s;
dp[0] = 1;
rep(i, ceil(n,2LL)){
swap(old, dp);
dp[0] += old[0];
dp[1] += old[0]*(s[i]-'A');
dp[1] += old[1]*26;
}
mint ans = dp[1];
string u = s.substr(0,n/2);
string t = u;
if(n%2) t.push_back(s[n/2]);
reverse(all(u));
t.insert(t.end(), all(u));
if(t <= s) ans += 1;
cout << ans.val() << endl;
}
return 0;
}
