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
import java.util.*;
import java.io.*;

public class Main {
    private static final int MOD = 1000000007, MAX = 2000000;
    private static final long[] fact = new long[MAX + 1];

    public static void main(String[] args) throws IOException {
        final long[] pow = new long[MAX + 1];
        pow[0] = 1;
        fact[0] = 1;
        for (int i = 1; i <= MAX; ++i) {
            pow[i] = (pow[i - 1] * 25) % MOD;
            fact[i] = (fact[i - 1] * i) % MOD;
        }

        final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int k = Integer.parseInt(br.readLine());
        String s = br.readLine();

        int n = s.length(), total = n + k;
        long res = pow(26, total);

        for (int i = 0; i < n; ++i) {
            res -= choose(total, i) * pow[total - i];
            res %= MOD;
            if (res < 0) {
                res += MOD;
            }
        }

        bw.write(Long.toString(res));
        bw.newLine();
        bw.close();
        br.close();
    }

    private static long pow(int base, int exponent) {
        long res = 1, extra = base;

        while (exponent > 0) {
            if ((exponent & 1) == 1) {
                res *= extra;
                res %= MOD;
            }
            extra *= extra;
            extra %= MOD;
            exponent >>= 1;
        }

        return res;
    }

    private static long choose(int n, int r) {
        return fact[n] * modInverse((int)fact[r], MOD) % MOD * modInverse((int)fact[n - r], MOD) % MOD;
    }

    private static int modInverse(int a, int m)
    {
        int m0 = m;
        int y = 0, x = 1;

        if (m == 1)
            return 0;

        while (a > 1)
        {
            int q = a / m;

            int t = m;

            m = a % m;
            a = t;
            t = y;

            y = x - q * y;
            x = t;
        }

        if (x < 0)
            x += m0;

        return x;
    }
}
