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;

const int64_t INT = 1000000007;

int64_t func1(int64_t x, int64_t y) {
  if(y == 0) {
    return 1;
  }
  else if(y % 2 == 0) {
    int64_t a = func1(x, y / 2);
    a = a * a % INT; 
    return a;
  }
  else {
    int64_t a = func1(x, y / 2); 
    a = a * a % INT;
    a = a * x % INT;
    return a;
  }
}

int main() {
  int K;
  string S;
  cin >> K >> S;
  int64_t ans = 0;
  int64_t n = S.size();
  int64_t combination = 1;
  for(int i = 2; i < n; i++) {
    combination = combination * func1(i, INT - 1);
  }
  for(int i = n - 1; i < n + K; i++) {
    int64_t keep = 1;
    keep = (func1(25, i - n + 1) * func1(26, n + K - i - 1)) % INT;
    keep = keep * combination % INT;
    combination = combination * (i + 1) % INT;
    combination = combination * func1(i - n + 2, INT - 2) % INT;
    ans += keep;
    ans %= INT;
  }
  cout << ans << endl;
}
