Problem p02632 (python)

Fixed submission:
FAST_IO = 0
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()
    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]

####

def solve(K, S):
    MOD = 10 ** 9 + 7
    N = len(S)
    N2 = N + K

    BIG =N2
    fac = [1, 1]
    for x in xrange(2, BIG+1):
        fac.append(fac[-1] * x  %MOD)
    inv = [1] * (BIG + 1)
    inv[BIG] = pow(fac[-1], MOD-2, MOD)
    for x in xrange(BIG-1, -1, -1):
        inv[x] = inv[x+1] * (x+1) % MOD

    def binom(n, k):
        ans = fac[n]
        ans *= inv[n-k]
        ans %= MOD
        
        ans *= inv[k]
        ans %= MOD
        return ans

    pow25 = [1]
    for x in xrange(1, BIG + 1):
        pow25.append(pow25[-1] * 25  %MOD)

    ans = 0
    for n in xrange(N, N2 + 1):
        ans += binom(N2, n)   * pow25[N2- n] % MOD
        ans %= MOD
    return ans

print solve(rri(), rr())

Buggy submission (verdict: Runtime Error):
MOD = 10 ** 9 + 7
K = int(input())
M = len(input())
N = M + K

pow25 = [1] * (N + 1)
fac = [1] * (N + 1)
inv = [1] * (N + 1)
for x in range(1, N + 1):
    fac[x] = fac[x - 1] * x % MOD
    pow25[x] = pow25[x - 1] * 25 % MOD
inv[N] = pow(fac[N], MOD-2, MOD)
for x in range(N - 1, -1, -1):
    inv[x] = inv[x + 1] * (x + 1) % MOD

def binom(n, k):
    return fac[n] * inv[n - k] % MOD * inv[k] % MOD

ans = 0
for k in range(M, N + 1):
    ans += binom(N, k) * pow25[N - k] % MOD
    ans %= MOD
print(ans)

Buggy submission (verdict: Runtime Error):
MOD = 10 ** 9 + 7
K = int(input())
M = len(input())
N = M + K

pow25 = [1] * (N + 1)
fac = [1] * (N + 1)
inv = [1] * (N + 1)
for x in range(1, N + 1):
    fac[x] = fac[x - 1] * x % MOD
    pow25[x] = pow25[x - 1] * 25 % MOD
inv[N] = pow(fac[N], MOD-2, MOD)
for x in range(N - 1, -1, -1):
    inv[x] = inv[x + 1] * (x + 1) % MOD

def binom(n, k):
    return fac[n] * inv[n - k] % MOD * inv[k] % MOD

pow25 = [1]

ans = 0
for k in range(M, N + 1):
    ans += binom(N, k) * pow25[N - k] % MOD
    ans %= MOD
print(ans)

Buggy submission (verdict: Runtime Error):
FAST_IO = 0
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()
    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]

####

from collections import defaultdict as ddic
def memo(f):
    """ Memoization decorator for functions taking one or more arguments. """
    class memodict(dict):
        def __init__(self, f):
            self.f = f
        def __call__(self, *args):
            return self[args]
        def __missing__(self, key):
            ret = self[key] = self.f(*key)
            return ret
    return memodict(f)

def brute(K,S):
    MOD = 10 ** 9 + 7
    N = len(S)
    N2 = N + K
    talk = ddic(int)
    #@memo
    def dp(i, j):
        if i> N2: return 0
        if i==N2:
            if j >= N:
                talk[j] += 1
            return +(j >= N)
        ans = dp(i+1, j+1)
        ans += 25 * dp(i+1, j)
        #ans %= MOD
        return ans
    ans = dp(0,0)
    #print("!", talk)
    return ans #dp(0,0)
    
def solve(K, S):
    MOD = 10 ** 9 + 7
    N = len(S)
    N2 = N + K
    # how many strings length N2 have S as substring?
    A = [ord(c)-ord('a') for c in S]

    BIG =10**6
    fac = [1, 1]
    for x in xrange(2, BIG+1):
        fac.append(fac[-1] * x  %MOD)
    inv = [1] * (BIG + 1)
    inv[BIG] = pow(fac[-1], MOD-2, MOD)
    for x in xrange(BIG-1, -1, -1):
        inv[x] = inv[x+1] * (x+1) % MOD

    def binom(n, k):
        ans = fac[n]
        ans *= inv[n-k]
        ans %= MOD
        
        ans *= inv[k]
        ans %= MOD
        return ans

    #pow26 = [1]
    pow25 = [1]
    for x in xrange(1, BIG + 1):
        pow25.append(pow25[-1] * 25  %MOD)
    #    pow26.append(pow26[-1] * 26  %MOD)
    #print pow25[:8]
    #print pow26[:8]
    ans = 0
    for n in xrange(N, N2 + 1):
        bns = binom(N2, n)   * pow25[N2- n] % MOD
        #print("!", binom(N2, n))
        #bns *= pow26[N
        ans+=bns
        ans %= MOD
    return ans

    #return binom(N2, N) % MOD

"""
def deltas(row):
    return [row[i+1] - row[i] for i in xrange(len(row) - 1)]
for k in range(1, 10):
    row = []
    for n in range(1, 10):
        x = solve(k, 'a' * n)
        row.append(x)
    print k, row
    print deltas(row)
    print deltas(deltas(row))
    print deltas(deltas(deltas(row)))
"""
#print solve(1, 'a'), brute(1, 'a')
#print solve(2, 'a'), brute(2, 'a')
#print solve(3, 'abc'), brute(3, 'abc')
print solve(rri(), rr())