Submission #463366


Source Code Expand

Copy
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

Submission Time
Task D - 表現の自由 ( Freedom of expression )
User yaketake08
Language Python (2.7.3)
Score 100
Code Size 994 Byte
Status
Exec Time 1299 ms
Memory 9772 KB

Judge Result

Set Name Score / Max Score Test Cases
All 100 / 100 00_max.txt, 00_max2.txt, 00_max3.txt, 00_min.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 01_rnd_20.txt, 01_rnd_21.txt, 01_rnd_22.txt, 01_rnd_23.txt, 01_rnd_24.txt, 01_rnd_25.txt, 01_rnd_26.txt, 01_rnd_27.txt, 01_rnd_28.txt, 01_rnd_29.txt, 04_primes_01.txt, 04_primes_02.txt
Case Name Status Exec Time Memory
00_max.txt 1260 ms 9772 KB
00_max2.txt 1286 ms 9732 KB
00_max3.txt 1267 ms 9764 KB
00_min.txt 56 ms 3380 KB
00_sample_01.txt 56 ms 3376 KB
00_sample_02.txt 57 ms 3376 KB
00_sample_03.txt 58 ms 3368 KB
00_sample_04.txt 69 ms 3492 KB
01_rnd_00.txt 544 ms 5924 KB
01_rnd_01.txt 206 ms 4124 KB
01_rnd_02.txt 76 ms 3492 KB
01_rnd_03.txt 509 ms 5680 KB
01_rnd_04.txt 453 ms 5424 KB
01_rnd_05.txt 579 ms 6060 KB
01_rnd_06.txt 224 ms 4260 KB
01_rnd_07.txt 251 ms 4388 KB
01_rnd_08.txt 1219 ms 9508 KB
01_rnd_09.txt 733 ms 6944 KB
01_rnd_10.txt 770 ms 7076 KB
01_rnd_11.txt 868 ms 7708 KB
01_rnd_12.txt 1105 ms 8996 KB
01_rnd_13.txt 584 ms 6180 KB
01_rnd_14.txt 683 ms 6696 KB
01_rnd_15.txt 270 ms 4512 KB
01_rnd_16.txt 890 ms 7724 KB
01_rnd_17.txt 1255 ms 9768 KB
01_rnd_18.txt 964 ms 8236 KB
01_rnd_19.txt 201 ms 4140 KB
01_rnd_20.txt 669 ms 6568 KB
01_rnd_21.txt 650 ms 6448 KB
01_rnd_22.txt 305 ms 4652 KB
01_rnd_23.txt 819 ms 7336 KB
01_rnd_24.txt 989 ms 8180 KB
01_rnd_25.txt 1155 ms 9188 KB
01_rnd_26.txt 732 ms 6952 KB
01_rnd_27.txt 545 ms 6004 KB
01_rnd_28.txt 585 ms 6176 KB
01_rnd_29.txt 1135 ms 9128 KB
04_primes_01.txt 1299 ms 9752 KB
04_primes_02.txt 1266 ms 9772 KB