| 29 | } |
| 30 | |
| 31 | int main(){ |
| 32 | scanf("%d %s", &N, S); |
| 33 | M = (int) strlen(S); |
| 34 | if(M > N){ |
| 35 | printf("0\n"); |
| 36 | return 0; |
| 37 | } |
| 38 | |
| 39 | for(int r = 0; r < M; r++){ |
| 40 | for(int c = 0; c < 26; c++){ |
| 41 | vector<char> pre; |
| 42 | for(int i = 0; i < r; i++) |
| 43 | pre.push_back(S[i]); |
| 44 | pre.push_back((char) (c+'A')); |
| 45 | |
| 46 | for(int k = 0; k < r+1; k++){ |
| 47 | if(good(pre, k)){ |
| 48 | best[c][r] = r-k+1; |
| 49 | break; |
| 50 | } |
| 51 | } |
| 52 | } |
| 53 | } |
| 54 | |
| 55 | dp[0][0] = 1; |
| 56 | for(int i = 1; i <= N; i++) |
| 57 | for(int j = 0; j < M; j++) |
| 58 | for(int c = 0; c < 26; c++) |
| 59 | dp[best[c][j]][i] = (dp[best[c][j]][i] + dp[j][i-1]) % MOD; |
| 60 | |
| 61 | ans = pow26(N); |
| 62 | for(int i = 0; i < M; i++) |
| 63 | ans = (ans - dp[i][N] + MOD) % MOD; |
| 64 | printf("%lld\n", ans); |
| 65 | } |