How many strings can be obtained by applying the following operation on a string S exactly K times: "choose one lowercase English letter and insert it somewhere"?

The answer can be enormous, so print it modulo (10^9+7).

Constraints

* K is an integer between 1 and 10^6 (inclusive).
* S is a string of length between 1 and 10^6 (inclusive) consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:


K
S


Output

Print the number of strings satisfying the condition, modulo (10^9+7).

Examples

Input

5
oof


Output

575111451


Input

37564
whydidyoudesertme


Output

318008117
#include <bits/stdc++.h>
using namespace std;

long f[2222222] = {1};
long inv(int a, int m) {
    long i = 1, j = 0;
    for(int b = m; a > 1; swap(i, j), swap(a, b)) {
        j = (j + b / a * (m - i)) % m;
        b %= a;
    }
    return i;
}
int main() {
    int k, p = 1e9 + 7;
    string s;
    cin >> k >> s;
    int n = k + s.length();
    for(int i = 1; i <= n; i++)
        f[i] = f[i - 1] * i % p;
    auto c = [&](int n, int r) {
        return f[n] * inv(f[r] * f[n - r] % p, p) % p;
    };
    long t = 1, r = 1;
    for(int i = 0; i < k; i++)
        (t *= 25) %= p, (r += c(n, i + 1) * t) %= p;
    cout << r << endl;
    return 0;
}
