Problem:


Score: 600 points

Problem Statement

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).

Sample Input 1

5
oof

Sample Output 1

575111451

For example, we can obtain proofend, moonwolf, and onionpuf, while we cannot obtain oofsix, oofelevennn, voxafolt, or fooooooo.

Sample Input 2

37564
whydidyoudesertme

Sample Output 2

318008117



Sample input:
5
oof


Sample output:
575111451

Submission status: Runtime Error

Solution code:

def resolve():
    MOD = 10 ** 9 + 7
    def COMinit(n, MOD):
        fact = [1, 1]
        fact_inv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fact.append((fact[-1] * i) % MOD)
            inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
            fact_inv.append((fact_inv[-1] * inv[i]) % MOD)
        return fact, fact_inv

    # 二項係数計算
    def Combination(n, k, MOD=10 ** 9 + 7):
        # fac, finv = COMinit(n, MOD)
        if n < k: return 0
        if n < 0 or k < 0: return 0
        ret = fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
        return ret

    K = int(input())
    S = input()
    N = len(S)

    fac, finv = COMinit(N + K, MOD)
    v = 1
    ans = 0
    for i in range(K + 1):
        ans += Combination(N + K, i) * v
        ans %= MOD
        v *= 25
        v %= MOD
    print(ans)

if __name__ == "__main__":
    
def resolve():
    MOD = 10 ** 9 + 7
    def COMinit(n, MOD):
        fact = [1, 1]
        fact_inv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fact.append((fact[-1] * i) % MOD)
            inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
            fact_inv.append((fact_inv[-1] * inv[i]) % MOD)
        return fact, fact_inv

    # 二項係数計算
    def Combination(n, k, MOD=10 ** 9 + 7):
        # fac, finv = COMinit(n, MOD)
        if n < k: return 0
        if n < 0 or k < 0: return 0
        ret = fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
        return ret

    K = int(input())
    S = input()
    N = len(S)

    fac, finv = COMinit(N + K, MOD)
    v = 1
    ans = 0
    for i in range(K + 1):
        ans += Combination(N + K, i) * v
        ans %= MOD
        v *= 25
        v %= MOD
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6 + 7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

K = int(input())
S = input()
n = len(S)
ans = 0
for i in range(K+1):
    ans += (cmb(i+n-1, n-1, mod) * pow(25, i, mod)%mod * pow(26, (K-i), mod)) % mod
print(ans%mod)

Submission status: Runtime Error

Solution code:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

K = int(input())
S = input()
n = len(S)
ans = 0
for i in range(K+1):
    ans += cmb(i+n-1, n-1, mod) * pow(25, i) * pow(26, (K-i))
print(ans%mod)

Submission status: Runtime Error

Solution code:
mod = 1000000007
fact = []
fact_inv = []
pow_ = []

def pow_ini(nn):
	pow_ = []
	pow_.append(nn)
	for j in range(62):
		nxt = pow_[j] * pow_[j]
		nxt %= mod
		pow_.append(nxt)
	return pow_

def pow1(k):
	global pow_
	ansk = 1
	for ntmp in range(62):
		if((k >> ntmp) % 2 == 1):
			ansk *= pow_[ntmp]
			ansk %= mod
	return ansk

def pow25(k):
	global pow25_
	ansk = 1
	for ntmp in range(62):
		if((k >> ntmp) % 2 == 1):
			ansk *= pow25_[ntmp]
			ansk %= mod
	return ansk

def pow26(k):
	global pow26_
	ansk = 1
	for ntmp in range(62):
		if((k >> ntmp) % 2 == 1):
			ansk *= pow26_[ntmp]
			ansk %= mod
	return ansk

def fact_ini(n):
	global fact
	global fact_inv
	global pow_
	for i in range(n + 1):
		fact.append(0)
		fact_inv.append(0)
	fact[0] = 1
	for i in range(1, n + 1, 1):
		fact_tmp = fact[i - 1] * i
		fact_tmp %= mod
		fact[i] = fact_tmp
	pow_ = pow_ini(fact[n])
	fact_inv[n] = pow1(mod - 2)
	for i in range(n - 1, -1, -1):
		fact_inv[i] = fact_inv[i + 1] * (i + 1)
		fact_inv[i] %= mod
	return

def nCm(n, m):
	assert(m >= 0)
	assert(n >= m)
	ans = fact[n] * fact_inv[m]
	ans %= mod
	ans *= fact_inv[n - m]
	ans %= mod
	return ans;

fact_ini(1100000)
pow25_ = pow_ini(25)
pow26_ = pow_ini(26)
K = int(input())
S = input()
N = len(S)
ans = 0
for k in range(0, K+1, 1):
	n = N + K - k
	anstmp = 1
	anstmp *= pow26(k)
	anstmp %= mod
	anstmp *= nCm(n - 1, N - 1)
	anstmp %= mod
	anstmp *= pow25(n - N)
	anstmp %= mod
	ans += anstmp
	ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

K = int(input())
S = input()
n = len(S)
ans = 0
for i in range(K+1):
    ans += cmb(i+n-1, n-1, mod) * pow(25, i) * pow(26, (K-i))
print(ans%mod)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cassert>
#define InfL 1000000000
#define InfLL 1000000000000000000LL
#define nmax_def 110000
#define Cmax_def 2200
#define mod 1000000007
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rrep(i,n) for(int (i)=(n-1);(i)>=(0);(i)--)
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<db> vd;


vl pow_;
vl pow_1;
vl pow_2;
void pow_ini(ll n) {
	pow_.clear();
	pow_.push_back(n);
	rep(j, 62) {
		ll nxt = pow_[j] * pow_[j];
		nxt %= mod;
		pow_.push_back(nxt);
	}
	return;
}
void pow_ini1(ll n) {
	pow_1.clear();
	pow_1.push_back(n);
	rep(j, 62) {
		ll nxt = pow_1[j] * pow_1[j];
		nxt %= mod;
		pow_1.push_back(nxt);
	}
	return;
}
void pow_ini2(ll n) {
	pow_2.clear();
	pow_2.push_back(n);
	rep(j, 62) {
		ll nxt = pow_2[j] * pow_2[j];
		nxt %= mod;
		pow_2.push_back(nxt);
	}
	return;
}

ll pow1(ll k) {
	ll ans = 1;
	rep(ntmp, 62) {
		if ((k >> ntmp) % 2 == 1) {
			ans *= pow_[ntmp];
			ans %= mod;
		}
	}
	return ans;
}
ll pow25(ll k) {
	ll ans = 1;
	rep(ntmp, 62) {
		if ((k >> ntmp) % 2 == 1) {
			ans *= pow_1[ntmp];
			ans %= mod;
		}
	}
	return ans;
}
ll pow26(ll k) {
	ll ans = 1;
	rep(ntmp, 62) {
		if ((k >> ntmp) % 2 == 1) {
			ans *= pow_2[ntmp];
			ans %= mod;
		}
	}
	return ans;
}

vl fact;
vl fact_inv;

void fact_ini(ll n) {
	fact.resize(n + 1);
	fact[0] = 1;
	for (ll i = 1; i <= n; i++) {
		ll fact_tmp = fact[i - 1] * i;
		fact_tmp %= mod;
		fact[i] = fact_tmp;
	}
	fact_inv.resize(n + 1);
	pow_ini(fact[n]);
	fact_inv[n] = pow1(mod - 2);
	for (ll i = n - 1; i >= 0; i--) {
		fact_inv[i] = fact_inv[i + 1] * (i + 1);
		fact_inv[i] %= mod;
	}
}

ll nCm(ll n, ll m) {
	assert(m >= 0);
	assert(n < fact.size());
	assert(n >= m);
	ll ans = fact[n] * fact_inv[m];
	ans %= mod;
	ans *= fact_inv[n - m];
	ans %= mod;
	return ans;
}

int main() {
	fact_ini(2200000);
	pow_ini1(25);
	pow_ini2(26);
	ll K;
	cin >> K;
	string S;
	cin >> S;
	ll N = S.length();
	ll ans = 0;
	for (ll k = 0; k <= K; k++) {
		ll n = N + K - k;
		ll anstmp = 1;
		anstmp *= pow26(k);
		anstmp %= mod;
		anstmp *= nCm(n - 1, N - 1);
		anstmp %= mod;
		anstmp *= pow25(n - N);
		anstmp %= mod;
		ans += anstmp;
		ans %= mod;

	}
	cout << ans << endl;
	return 0;
}

Submission status: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
MOD = 10**9+7
fac = [1 for k in range(1000010)]
inv = [1 for k in range(1000010)]
finv = [1 for k in range(1000010)]
P25 = [1 for k in range(1000010)]
P26 = [1 for k in range(1000010)]
P25[1] = 25
P26[1] = 26
for k in range(2,1000010):
    fac[k] = (fac[k-1]*k)%MOD
    inv[k] = (MOD - inv[MOD%k] * (MOD // k))%MOD
    finv[k] = (finv[k - 1] * inv[k]) % MOD;
    P26[k] = (P26[k-1]*26) % MOD
    P25[k] = (P25[k-1]*25) % MOD

def nCr(n,r):
    return (fac[n]*finv[r]*finv[n-r])%MOD
def main():
    K = int(input())
    S = input()
    ans = 0
    for k in range(K+1):
#        print(k,nCr(K-k+len(S)-1,len(S)-1))
        ans += nCr(K-k+len(S)-1,len(S)-1)*P25[K-k]*P26[k]
        ans %= MOD
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
MOD = 10**9+7
fac = [1 for k in range(100010)]
inv = [1 for k in range(100010)]
finv = [1 for k in range(100010)]
P25 = [1 for k in range(100010)]
P26 = [1 for k in range(100010)]
P25[1] = 25
P26[1] = 26
for k in range(2,100010):
    fac[k] = (fac[k-1]*k)%MOD
    inv[k] = (MOD - inv[MOD%k] * (MOD // k))%MOD
    finv[k] = (finv[k - 1] * inv[k]) % MOD;
    P26[k] = (P26[k-1]*26) % MOD
    P25[k] = (P25[k-1]*25) % MOD

def nCr(n,r):
    return (fac[n]*finv[r]*finv[n-r])%MOD
def main():
    K = int(input())
    S = input()
    ans = 0
    for k in range(K+1):
#        print(k,nCr(K-k+len(S)-1,len(S)-1))
        ans += nCr(K-k+len(S)-1,len(S)-1)*P25[K-k]*P26[k]
        ans %= MOD
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
readline=sys.stdin.readline

K = int(readline())
S = readline().rstrip()
N = len(S)

DIV = 10 ** 9 + 7
n = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % DIV )
    inverse.append( ( -inverse[DIV % i] * (DIV//i) ) % DIV )
    g2.append( (g2[-1] * inverse[-1]) % DIV )

def nCr(n, r, DIV):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % DIV
  
# N = |S|とする
# N + Kの長さの文字列で、N～N + K文字までが固定で、あとは任意の25文字
# の数が答え
ans = 0
for i in range(N,N + K + 1):
  # N + K文字からi文字を選ぶ場合の数
  pat = nCr(N + K, i ,DIV)
  
  # 残りN + K - i文字に対して25通り選べる場合の数
  pat *= pow(25, N + K - i, DIV)
  pat %= DIV
  ans += pat
  ans %= DIV
print(ans)

Submission status: Runtime Error

Solution code:
#input
K = int(input())
S = str(input())

#output
# (o以外) o (o以外) o (f以外) f (何でも)


#こちらもmodで割った余り。maxが決まっていて、大きくない時はこちらが早い。
mod = pow(10, 9) + 7

n_ = pow(10, 6) + 1
fun = [1] * (n_+1)
for i in range(1, n_+1):
    fun[i] = fun[i-1] * i % mod
rev = [1] * (n_+1)
rev[n_] = pow(fun[n_], mod-2, mod)
for i in range(n_-1, 0, -1):
    rev[i] = rev[i+1] * (i+1) % mod
def cmb(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n] * rev[r] % mod * rev[n-r] % mod

#重複組み合わせはH(n, r) = cmb(n+r-1, r)

N = len(S)
answer = 0
for i in range(K+1):
    answer += pow(25, i, mod) * pow(26, K-i, mod) * cmb(N-1+i, N-1) % mod
print(answer % mod)

Submission status: Runtime Error

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    K = int(input())
    S = str(input())

    #output
    # (o以外) o (o以外) o (f以外) f (何でも)


    #こちらもmodで割った余り。maxが決まっていて、大きくない時はこちらが早い。
    mod = pow(10, 9) + 7

    n_ = pow(10, 6) + 1
    fun = [1] * (n_+1)
    for i in range(1, n_+1):
        fun[i] = fun[i-1] * i % mod
    rev = [1] * (n_+1)
    rev[n_] = pow(fun[n_], mod-2, mod)
    for i in range(n_-1, 0, -1):
        rev[i] = rev[i+1] * (i+1) % mod
    def cmb(n,r):
        if n <= 0 or r < 0 or r > n: return 0
        return fun[n] * rev[r] % mod * rev[n-r] % mod

    #重複組み合わせはH(n, r) = cmb(n+r-1, r)

    N = len(S)
    answer = 0
    for i in range(K+1):
        answer += pow(25, i, mod) * pow(26, K-i, mod) * cmb(N-1+i, N-1) % mod
    print(answer % mod)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def solve():
    K = int(input())
    S = input()
    N = len(S)

    MOD = 10**9+7
    n = N+K
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    
    for i in range(1,n+1):
    fac[i] = i*fac[i-1]%MOD
    rev[i] = pow(fac[i], MOD-2, MOD)
    
    comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD

    ans = 0
    for i in range(K+1):
        ans += pow(26, K-i, MOD) * pow(25, i, MOD) * comb(N+i-1, i)
        ans %= MOD
    print(ans)


solve()

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

k = I()
s = S()
l = len(s)
n = k + s + 1
fac = [1] * (n + 1)
inv = [1] * (n + 1)
twentyFive = [1] * (n + 1)
twentySix = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod
    twentyFive[j] = twentyFive[j - 1] * 25 % mod
    twentySix[j] = twentySix[j - 1] * 26 % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod




ans = 0
for i in range(k + 1):
    ans += comb(l - 1 + i, i) * twentyFive[i] % mod * twentySix[k - i] % mod
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

k = I()
s = S()
l = len(s)
n = k * 2 + 1
fac = [1] * (n + 1)
inv = [1] * (n + 1)
twentyFive = [1] * (n + 1)
twentySix = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod
    twentyFive[j] = twentyFive[j - 1] * 25 % mod
    twentySix[j] = twentySix[j - 1] * 26 % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod




ans = 0
for i in range(k + 1):
    ans += comb(l - 1 + i, i) * twentyFive[i] % mod * twentySix[k - i] % mod
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

k = I()
s = S()
l = len(s)
n = k * 2 + 1
fac = [1] * (n + 1)
inv = [1] * (n + 1)
twentyFive = [1] * (n + 1)
twentySix = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod
    twentyFive[j] = twentyFive[j - 1] * 25 % mod
    twentySix[j] = twentySix[j - 1] * 26 % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod




ans = 0
for i in range(k + 1):
    ans += comb(l - 1 + i, i) * twentyFive[i] * twentySix[k - i]
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
K=int(input())
s=input()
S=len(s)
mod=10**9+7
MAX_N=10**6+10
fact=[1]
fact_inv=[0]*(MAX_N+4)
for i in range(MAX_N+3):
  fact.append(fact[-1]*(i+1)%mod)

fact_inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(MAX_N+2,-1,-1):
  fact_inv[i]=fact_inv[i+1]*(i+1)%mod

def mod_comb_k(n,k,mod):
  return fact[n]*fact_inv[k]%mod*fact_inv[n-k] %mod

cnt=0
for i in range(K+1):
  a=(pow(26,i,mod)*pow(25,K-i,mod))*(mod_comb_k(K+S-i-1,S-1,mod))
  a%=mod
  cnt+=a
  cnt%=mod
print(cnt)

Submission status: Runtime Error

Solution code:
K=int(input())
s=input()
S=len(s)
mod=10**9+7
MAX_N=10**6
fact=[1]
fact_inv=[0]*(MAX_N+4)
for i in range(MAX_N+3):
  fact.append(fact[-1]*(i+1)%mod)

fact_inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(MAX_N+2,-1,-1):
  fact_inv[i]=fact_inv[i+1]*(i+1)%mod

def mod_comb_k(n,k,mod):
  return fact[n]*fact_inv[k]%mod*fact_inv[n-k] %mod

cnt=0
for i in range(K+1):
  a=(pow(26,i,mod)*pow(25,K-i,mod))*(mod_comb_k(K+S-i-1,S-1,mod))
  a%=mod
  cnt+=a
  cnt%=mod
print(cnt)

Submission status: Runtime Error

Solution code:
 
# from math import factorial as fac
from collections import defaultdict
# from copy import deepcopy
import sys, math
f = None
try:
	f = open('q1.input', 'r')
except IOError:
	f = sys.stdin
if 'xrange' in dir(__builtins__):
	range = xrange
# print(f.readline())
sys.setrecursionlimit(10**2)

	
def print_case_iterable(case_num, iterable):
	print("Case #{}: {}".format(case_num," ".join(map(str,iterable))))

def print_case_number(case_num, iterable):
	print("Case #{}: {}".format(case_num,iterable))

def print_iterable(A):
	print (' '.join(A))

def read_int():
	return int(f.readline().strip())
def read_int_array():
	return [int(x) for x in f.readline().strip().split(" ")]
def rns():
	a =  [x for x in f.readline().split(" ")]
	return int(a[0]), a[1].strip()
def read_string():
	return list(f.readline().strip())
def ri():
	return int(f.readline().strip())
def ria():
	return [int(x) for x in f.readline().strip().split(" ")]
def rns():
	a =  [x for x in f.readline().split(" ")]
	return int(a[0]), a[1].strip()
def rs():
	return list(f.readline().strip())
def bi(x):
	return bin(x)[2:]





from collections import deque
import math
NUMBER = 10**9 + 7
# NUMBER = 998244353
def factorial(n) : 
	M = NUMBER
	f = 1
  
	for i in range(1, n + 1):  
		f = (f * i) % M # Now f never can  
						# exceed 10^9+7  
	return f
def mult(a,b):
	return (a * b) % NUMBER

def minus(a , b):
	return (a - b) % NUMBER

def plus(a , b):
	return (a + b) % NUMBER

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		g, y, x = egcd(b % a, a)
		return (g, x - (b // a) * y, y)

def modinv(a):
	m = NUMBER
	g, x, y = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
def choose(n,k):
	if n < k:
		assert false
	return  mult(factorial(n), modinv(mult(factorial(k),factorial(n-k)))) % NUMBER
from collections import deque, defaultdict 
import heapq


from types import GeneratorType
def bootstrap(f, stack=[]):
	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to

	return wrappedfunc


def dfs(g, timeIn, timeOut,depths,parents): 
	# assign In-time to node u 
	cnt = 0
	# node, neig_i, parent, depth
	stack = [[1,0,0,0]]
	while stack:
		v,neig_i,parent,depth = stack[-1]
		parents[v] = parent
		depths[v] = depth
		# print (v)
		if neig_i == 0:
			timeIn[v] = cnt    
			cnt+=1
		while neig_i < len(g[v]):
			u = g[v][neig_i]
			if u == parent:
				neig_i+=1
				continue
			stack[-1][1] = neig_i + 1
			stack.append([u,0,v,depth+1])
			break
		if neig_i == len(g[v]):
			stack.pop()
			timeOut[v] = cnt
			cnt += 1
  
# def isAncestor(u: int, v: int, timeIn: list, timeOut: list) -> str: 
# 	return timeIn[u] <= timeIn[v] and timeOut[v] <= timeOut[u] 

cnt = 0
@bootstrap
def dfs(v,adj,timeIn, timeOut,depths,parents,parent=0,depth=0):
	global cnt
	parents[v] = parent
	depths[v] = depth
	timeIn[v] = cnt
	cnt+=1
	for u in adj[v]:
		if u == parent:
			continue
		yield dfs(u,adj,timeIn,timeOut,depths,parents,v,depth+1)
	timeOut[v] = cnt
	cnt+=1
	yield 


def solution(s,n):
	# fact = [1]*(10**6+1)
	# for i in range(1,10**6+1):
	# 	fact[i] = (fact[i-1]*i)%NUMBER
	p = NUMBER
	summ = 0
	k = len(s)
	n = n+k
	d = 26
	mxn = 10**6
	pows = [0]*(mxn+1)
	for i in range(1,mxn+1):
		pows[i] = pow(i,p-2,p)
	chooses = [1]*(mxn+1)
	for i in range(1,mxn+1):
		chooses[i] = (chooses[i-1] * (n-(i-1)) *(pows[i]))%p
	dpows = [0]*(mxn+1)
	for i in range(1,mxn+1):
		dpows[i] = pow(d-1,i,p)	
	# def chooseb(l,r):
	# 	return mult(fact[l],pow(mult(fact[r],fact[l-r]),p-2,p))
	for j in range(n-k+1):
		# print(j)
		summ=plus(summ,mult(chooses[j+k],dpows[n-k-j]))
		# summ=mult(summ,)
	return summ + 1
	
def main():
	T = 1
	# T = ri()
	for i in range(T):
		n = ri()
		s = rs()
		# a = ria()
		# n,k = ria()
		# a=ria()

		x = solution(s,n)
		if 'xrange' not in dir(__builtins__):
			print(x)
		else:
			print >>output,str(x)# "Case #"+str(i+1)+':',
	if 'xrange' in dir(__builtins__):
		print(output.getvalue())
		output.close()

if 'xrange' in dir(__builtins__):
	import cStringIO
	output = cStringIO.StringIO()
#example usage:
#    for l in res:
#       print >>output, str(len(l)) + ' ' +  ' '.join(l)

if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
 
# from math import factorial as fac
from collections import defaultdict
# from copy import deepcopy
import sys, math
f = None
try:
	f = open('q1.input', 'r')
except IOError:
	f = sys.stdin
if 'xrange' in dir(__builtins__):
	range = xrange
# print(f.readline())
sys.setrecursionlimit(10**2)

	
def print_case_iterable(case_num, iterable):
	print("Case #{}: {}".format(case_num," ".join(map(str,iterable))))

def print_case_number(case_num, iterable):
	print("Case #{}: {}".format(case_num,iterable))

def print_iterable(A):
	print (' '.join(A))

def read_int():
	return int(f.readline().strip())
def read_int_array():
	return [int(x) for x in f.readline().strip().split(" ")]
def rns():
	a =  [x for x in f.readline().split(" ")]
	return int(a[0]), a[1].strip()
def read_string():
	return list(f.readline().strip())
def ri():
	return int(f.readline().strip())
def ria():
	return [int(x) for x in f.readline().strip().split(" ")]
def rns():
	a =  [x for x in f.readline().split(" ")]
	return int(a[0]), a[1].strip()
def rs():
	return list(f.readline().strip())
def bi(x):
	return bin(x)[2:]





from collections import deque
import math
NUMBER = 10**9 + 7
# NUMBER = 998244353
def factorial(n) : 
	M = NUMBER
	f = 1
  
	for i in range(1, n + 1):  
		f = (f * i) % M # Now f never can  
						# exceed 10^9+7  
	return f
def mult(a,b):
	return (a * b) % NUMBER

def minus(a , b):
	return (a - b) % NUMBER

def plus(a , b):
	return (a + b) % NUMBER

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		g, y, x = egcd(b % a, a)
		return (g, x - (b // a) * y, y)

def modinv(a):
	m = NUMBER
	g, x, y = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
def choose(n,k):
	if n < k:
		assert false
	return  mult(factorial(n), modinv(mult(factorial(k),factorial(n-k)))) % NUMBER
from collections import deque, defaultdict 
import heapq


from types import GeneratorType
def bootstrap(f, stack=[]):
	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to

	return wrappedfunc


def dfs(g, timeIn, timeOut,depths,parents): 
	# assign In-time to node u 
	cnt = 0
	# node, neig_i, parent, depth
	stack = [[1,0,0,0]]
	while stack:
		v,neig_i,parent,depth = stack[-1]
		parents[v] = parent
		depths[v] = depth
		# print (v)
		if neig_i == 0:
			timeIn[v] = cnt    
			cnt+=1
		while neig_i < len(g[v]):
			u = g[v][neig_i]
			if u == parent:
				neig_i+=1
				continue
			stack[-1][1] = neig_i + 1
			stack.append([u,0,v,depth+1])
			break
		if neig_i == len(g[v]):
			stack.pop()
			timeOut[v] = cnt
			cnt += 1
  
# def isAncestor(u: int, v: int, timeIn: list, timeOut: list) -> str: 
# 	return timeIn[u] <= timeIn[v] and timeOut[v] <= timeOut[u] 

cnt = 0
@bootstrap
def dfs(v,adj,timeIn, timeOut,depths,parents,parent=0,depth=0):
	global cnt
	parents[v] = parent
	depths[v] = depth
	timeIn[v] = cnt
	cnt+=1
	for u in adj[v]:
		if u == parent:
			continue
		yield dfs(u,adj,timeIn,timeOut,depths,parents,v,depth+1)
	timeOut[v] = cnt
	cnt+=1
	yield 


def solution(s,n):
	# fact = [1]*(10**6+1)
	# for i in range(1,10**6+1):
	# 	fact[i] = (fact[i-1]*i)%NUMBER
	p = NUMBER
	summ = 0
	k = len(s)
	n = n+k
	d = 26
	mxn = 10**6
	pows = [0]*(mxn+1)
	for i in range(1,mxn+1):
		pows[i] = pow(i,p-2,p)
	chooses = [1]*(mxn+1)
	for i in range(1,mxn+1):
		chooses[i] = (chooses[i-1] * (n-(i-1)) *(pows[i]))%p
	dpows = [0]*(mxn+1)
	for i in range(1,mxn+1):
		dpows[i] = pow(d-1,i,p)	
	# def chooseb(l,r):
	# 	return mult(fact[l],pow(mult(fact[r],fact[l-r]),p-2,p))
	for j in range(n-k+1):
		# print(j)
		summ=plus(summ,mult(chooses[j+k],dpows[n-k-j]))
		# summ=mult(summ,)
	return summ
	
def main():
	T = 1
	# T = ri()
	for i in range(T):
		n = ri()
		s = rs()
		# a = ria()
		# n,k = ria()
		# a=ria()

		x = solution(s,n)
		if 'xrange' not in dir(__builtins__):
			print(x)
		else:
			print >>output,str(x)# "Case #"+str(i+1)+':',
	if 'xrange' in dir(__builtins__):
		print(output.getvalue())
		output.close()

if 'xrange' in dir(__builtins__):
	import cStringIO
	output = cStringIO.StringIO()
#example usage:
#    for l in res:
#       print >>output, str(len(l)) + ' ' +  ' '.join(l)

if __name__ == '__main__':
	main()