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;
#define int long long
#define IOS ios_base::sync_with_stdio(0);cin.tie(0)
/* start */

const int mod = 1e9 + 7;
const int N = 2e6 + 9;

int fat[N], inv[N];

int fastexp(int b, int e) {
   if(e == 0) return 1;
   int ans = fastexp(b, e/2);
   ans = (ans*ans)%mod;
   if(e%2 == 1) ans = (ans * b)%mod;
   return ans;
}

void init() {
   fat[0] = fat[1] = 1;
   inv[0] = inv[1] = 1;
   for(int i = 2; i < N; i++) {
      fat[i] = (i * fat[i-1])%mod;
      inv[i] = fastexp(fat[i], mod - 2);
   }
}

int comb(int a, int b) {
   return fat[a] * inv[b] % mod * inv[a-b] % mod;
}

signed main(){
   IOS;
   init();
   int k; cin >> k;
   string s; cin >> s;
   int n = s.size();
   int ans = 0;
   for(int i = 0; i <= k; i++) {
      ans = (ans + fastexp(25, i) * fastexp(26, k - i) % mod * comb(i + n - 1, n - 1) % mod) % mod;
   }
   cout << ans << "\n";
}