Submission #463366

---

Source Code Expand

import math
MOD = 10**9+7
n, m = map(int, raw_input().split())
p = []
minus = 0
if n<0:
    minus = 1
    n = -n

def extgcd(a, b):
    if b:
        d, y, x = extgcd(b, a%b)
        y -= (a/b)*x
        return d, x, y
    else:
        return a, 1, 0
M = m+50
fact = [0] * (M+1)
frev = [0] * (M+1)
fact[0] = frev[0] = 1
for i in xrange(1, M+1):
    fact[i] = (i * fact[i-1]) % MOD
    c = extgcd(fact[i], MOD)[1]
    frev[i] = (c + MOD) % MOD
def comb(n, k):
    rr = (frev[n-k] * frev[k]) % MOD
    return (fact[n] * rr) % MOD

i = 2
sq = math.sqrt(n)
while n>1 and i<=sq:
    if n%i==0:
        cnt = 0
        while n%i==0:
            n /= i
            cnt += 1
        p.append(cnt)
        sq = math.sqrt(n)
    i += 1
if n>1:
    p.append(1)
ans = 1
for i in xrange(len(p)):
    ans = (ans * comb(p[i]+m-1, m-1)) % MOD
sig = 0
for i in xrange((m-minus)/2+1):
    sig = (sig + comb(m, 2*i+minus)) % MOD
ans = (ans * sig) % MOD
print ans

Submission Info

Judge Result