結果
| 問題 | No.214 素数サイコロと合成数サイコロ (3-Medium) |
| ユーザー |
 Min_25
|
| 提出日時 | 2015-05-22 23:49:34 |
| 言語 | PyPy2 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 436 ms / 3,000 ms |
| コード長 | 28,994 bytes |
| コンパイル時間 | 1,546 ms |
| コンパイル使用メモリ | 76,200 KB |
| 実行使用メモリ | 89,468 KB |
| 最終ジャッジ日時 | 2024-07-06 05:38:55 |
| 合計ジャッジ時間 | 3,624 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 421 ms
89,224 KB |
| testcase_01 | AC | 411 ms
89,000 KB |
| testcase_02 | AC | 436 ms
89,468 KB |
ソースコード
LARGE_PRIMES = [
999990011, 999990029, 999990071, 999990091, 999990097, 999990109, 999990143, 999990227, 999990239, 999990259,
999990289, 999990293, 999990301, 999990319, 999990347, 999990353, 999990359, 999990373, 999990419, 999990421,
999990461, 999990479, 999990517, 999990569, 999990571, 999990581, 999990583, 999990599, 999990631, 999990709,
999990763, 999990787, 999990809, 999990833, 999990841, 999990851, 999990853, 999990857, 999990869, 999990877,
999990911, 999990913, 999990923, 999990931, 999990947, 999990973, 999990977, 999990991, 999990997, 999991009,
999991037, 999991061, 999991063, 999991067, 999991081, 999991123, 999991133, 999991141, 999991151, 999991163,
999991207, 999991229, 999991231, 999991241, 999991277, 999991283, 999991301, 999991327, 999991331, 999991339,
999991351, 999991367, 999991373, 999991423, 999991441, 999991453, 999991463, 999991469, 999991507, 999991547,
999991571, 999991591, 999991627, 999991661, 999991669, 999991819, 999991829, 999991843, 999991847, 999991873,
999991919, 999991921, 999991973, 999992023, 999992029, 999992039, 999992057, 999992087, 999992099, 999992101,
999992107, 999992111, 999992129, 999992131, 999992153, 999992177, 999992209, 999992221, 999992263, 999992267,
999992281, 999992293, 999992339, 999992347, 999992359, 999992387, 999992407, 999992423, 999992447, 999992509,
999992527, 999992537, 999992573, 999992579, 999992639, 999992641, 999992647, 999992677, 999992723, 999992731,
999992737, 999992753, 999992759, 999992783, 999992837, 999992867, 999992891, 999992899, 999992927, 999992977,
999992999, 999993031, 999993041, 999993061, 999993067, 999993083, 999993119, 999993143, 999993179, 999993221,
999993229, 999993289, 999993311, 999993367, 999993377, 999993439, 999993461, 999993469, 999993481, 999993571,
999993581, 999993583, 999993623, 999993637, 999993641, 999993653, 999993671, 999993697, 999993707, 999993719,
999993721, 999993733, 999993739, 999993763, 999993791, 999993811, 999993817, 999993821, 999993823, 999993833,
999993851, 999993887, 999993899, 999993901, 999993913, 999993947, 999993971, 999994003, 999994007, 999994081,
999994091, 999994097, 999994123, 999994129, 999994157, 999994159, 999994189, 999994201, 999994241, 999994267,
999994273, 999994277, 999994297, 999994309, 999994313, 999994321, 999994337, 999994343, 999994357, 999994379,
999994381, 999994397, 999994423, 999994427, 999994433, 999994439, 999994487, 999994507, 999994531, 999994537,
999994549, 999994603, 999994609, 999994613, 999994649, 999994651, 999994691, 999994693, 999994703, 999994741,
999994747, 999994753, 999994763, 999994771, 999994781, 999994813, 999994823, 999994837, 999994843, 999994861,
999994867, 999994883, 999994903, 999994913, 999994951, 999994973, 999994979, 999994987, 999995093, 999995107,
999995111, 999995141, 999995239, 999995257, 999995261, 999995273, 999995291, 999995341, 999995377, 999995393,
999995413, 999995419, 999995431, 999995531, 999995561, 999995567, 999995599, 999995611, 999995621, 999995627,
999995629, 999995651, 999995663, 999995677, 999995681, 999995701, 999995713, 999995741, 999995749, 999995803,
999995809, 999995813, 999995819, 999995903, 999995911, 999995921, 999995959, 999995993, 999996007, 999996029,
999996031, 999996037, 999996043, 999996071, 999996073, 999996091, 999996113, 999996131, 999996149, 999996181,
999996199, 999996223, 999996227, 999996247, 999996259, 999996269, 999996301, 999996307, 999996311, 999996317,
999996329, 999996341, 999996359, 999996383, 999996407, 999996469, 999996493, 999996541, 999996587, 999996611,
999996643, 999996649, 999996671, 999996677, 999996689, 999996707, 999996709, 999996727, 999996749, 999996779,
999996827, 999996901, 999996913, 999996919, 999996983, 999996989, 999997021, 999997049, 999997067, 999997081,
999997099, 999997133, 999997181, 999997237, 999997241, 999997249, 999997267, 999997279, 999997301, 999997309,
999997331, 999997357, 999997403, 999997457, 999997489, 999997543, 999997561, 999997567, 999997571, 999997577,
999997589, 999997627, 999997639, 999997643, 999997673, 999997679, 999997697, 999997717, 999997769, 999997771,
999997787, 999997793, 999997811, 999997871, 999997891, 999997967, 999998003, 999998017, 999998023, 999998059,
999998081, 999998107, 999998119, 999998137, 999998141, 999998143, 999998147, 999998173, 999998183, 999998203,
999998243, 999998261, 999998269, 999998309, 999998339, 999998369, 999998423, 999998459, 999998501, 999998507,
999998509, 999998533, 999998537, 999998563, 999998609, 999998617, 999998621, 999998627, 999998639, 999998641,
999998653, 999998663, 999998683, 999998687, 999998689, 999998693, 999998777, 999998789, 999998801, 999998843,
999998863, 999998869, 999998903, 999998917, 999998921, 999998929, 999998957, 999998959, 999998971, 999998981,
999999001, 999999017, 999999029, 999999043, 999999059, 999999067, 999999103, 999999107, 999999113, 999999131,
999999137, 999999151, 999999163, 999999181, 999999191, 999999193, 999999197, 999999223, 999999229, 999999323,
999999337, 999999353, 999999391, 999999433, 999999487, 999999491, 999999503, 999999527, 999999541, 999999587,
999999599, 999999607, 999999613, 999999667, 999999677, 999999733, 999999739, 999999751, 999999757, 999999761,
999999797, 999999883, 999999893, 999999929, 999999937
]
def random_matrix(size, fr, to, ratio=1.0):
return [[(rand(fr, to) if random.random() < ratio else 0) for _ in range(size)] for _ in range(size)]
def random_vector(size, fr, to, ratio=1.0):
return [(rand(fr, to) if random.random() < ratio else 0) for _ in range(size)]
def derivative(poly):
s = len(poly) - 1
return [poly[i] * (s - i) for i in range(s)]
def _poly_mul(poly1, poly2):
ret = [0] * (len(poly1) + len(poly2) - 1)
for i in range(len(poly2)):
if poly2[i] == 0:
continue
coef = poly2[i]
for j in range(len(poly1)):
ret[i + j] += coef * poly1[j]
return ret
def poly_mul_karatsuba(poly1, poly2, threshold=16):
size = len(poly1)
if size >= threshold:
size_l = (size + 1) // 2
size_h = size - size_l
p1 = poly_mul_karatsuba(poly1[:size_h], poly2[:size_h], threshold)
p2 = poly_mul_karatsuba(poly1[size_h:], poly2[size_h:], threshold)
q1 = poly1[size_h:]
q2 = poly2[size_h:]
ofs = size_l - size_h
for i in range(size_h):
q1[ofs + i] += poly1[i]
q2[ofs + i] += poly2[i]
p3 = poly_mul_karatsuba(q1, q2, threshold)
ret = p1
ret.extend([0])
ret.extend(p2)
for i in range(size_l * 2 - 1):
p3[i] -= ret[2 * size_h + i]
for i in range(size_h * 2 - 1):
p3[ofs * 2 + i] -= ret[i]
ofs = 2 * size - 3 * size_l
for i in range(size_l * 2 - 1):
ret[ofs + i] += p3[i]
return ret
else:
return _poly_mul(poly1, poly2)
def _pack(pack, shamt):
size = len(pack)
while size > 1:
npack = []
for i in range(0, size - 1, 2):
npack.append(pack[i] | (pack[i+1] << shamt))
if size & 1:
npack.append(pack[-1])
pack = npack
size = (size + 1) >> 1
shamt <<= 1
return pack[0]
def _pack1(seq, shamt):
M = _pack(seq, shamt)
size = len(seq) * 2 - 1
block_size = 1 << ilog2(size - 1)
return M, shamt * block_size
def _pack2(seq1, seq2, shamt):
M1 = _pack(seq1, shamt)
M2 = _pack(seq2, shamt)
size = len(seq1) + len(seq2) - 1
block_size = 1 << ilog2(size - 1)
return M1, M2, shamt * block_size
def pack_sequence(seq):
max_bits = max([c.bit_length() for c in seq])
size = len(seq)
shamt = (max_bits * 2 + size.bit_length())
return _pack1(seq, shamt)
def pack_sequence_mod(seq, mod):
size = len(seq)
max_value = (mod - 1) ** 2 * size
shamt = max_value.bit_length()
return _pack1(seq, shamt)
def pack_sequence2(seq1, seq2):
max_bits_1 = max([c.bit_length() for c in seq1])
max_bits_2 = max([c.bit_length() for c in seq2])
size = min(len(seq1), len(seq2))
shamt = (max_bits_1 + max_bits_2 + size.bit_length())
return _pack2(seq1, seq2, shamt)
def pack_sequence2_mod(seq1, seq2, mod):
size = min(len(seq1), len(seq2))
max_value = (mod - 1) ** 2 * size
shamt = max_value.bit_length()
return _pack2(seq1, seq2, shamt)
def unpack_sequence(M, size, shamt):
needed_sizes = []
s = size
while s > 1:
needed_sizes.append(s)
s = (s + 1) >> 1
ret = [M]
for needed_size in needed_sizes[::-1]:
mask = (1 << shamt) - 1
nret = []
for c in ret:
nret.append(c & mask)
nret.append(c >> shamt)
ret = nret[:needed_size]
shamt >>= 1
return ret
def poly_mul_builtin(poly1, poly2):
M1, M2, shamt = pack_sequence2(poly1, poly2)
size = len(poly1) + len(poly2) - 1
return unpack_sequence(M1 * M2, size, shamt)
def poly_mul(poly1, poly2, threshold=16, use_builtin=False):
t = type(poly1[0])
if use_builtin and len(poly1) >= threshold and (t == int or t == long):
return poly_mul_builtin(poly1, poly2)
else:
if len(poly1) == len(poly2):
return poly_mul_karatsuba(poly1, poly2, threshold)
else:
return _poly_mul(poly1, poly2)
def poly_square_builtin(poly):
M, shamt = pack_sequence(poly)
size = len(poly) * 2 - 1
return unpack_sequence(M ** 2, size, shamt)
def _poly_square(poly):
size = len(poly)
ret = [0] * (size * 2 - 1)
for i in range(size):
ret[2 * i] = poly[i] * poly[i]
for i in range(size):
coef = 2 * poly[i]
for j in range(i + 1, size):
ret[i + j] += coef * poly[j]
return ret
def poly_square_karatsuba(poly, threshold=16):
size = len(poly)
if size >= threshold:
size_l = (size + 1) // 2
size_h = size - size_l
p1 = poly_square_karatsuba(poly[:size_h], threshold)
p2 = poly_square_karatsuba(poly[size_h:], threshold)
S = poly[size_h:]
ofs = size_l - size_h
for i in range(size_h):
S[ofs + i] += poly[i]
p3 = poly_square_karatsuba(S, threshold)
ret = p1
ret.extend([0])
ret.extend(p2)
for i in range(size_l * 2 - 1):
p3[i] -= ret[2 * size_h + i]
for i in range(size_h * 2 - 1):
p3[ofs * 2 + i] -= ret[i]
ofs = 2 * size - 3 * size_l
for i in range(size_l * 2 - 1):
ret[ofs + i] += p3[i]
return ret
else:
return _poly_square(poly)
def poly_square(poly, threshold=16, use_builtin=False):
t = type(poly[0])
if use_builtin and len(poly) >= threshold and (t == int or t == long):
return poly_square_builtin(poly)
else:
if len(poly) >= threshold:
return poly_square_karatsuba(poly)
else:
return _poly_square(poly)
def poly_pow(poly, e, threshold=16):
ret = [1]
if e == 0:
return ret
mask = 1 << (e.bit_length() - 1)
ret = [1]
while mask:
if e & mask:
ret = poly_mul(ret, poly, threshold, False)
mask >>= 1
if not mask:
break
ret = poly_square(ret, threshold, False)
return ret
def poly_inverse(poly, size):
assert(poly[0] == 1)
degs = []
deg = size - 1
while deg:
degs.append(deg)
deg >>= 1
poly2 = poly[:]
if len(poly2) < size:
poly2.extend([0] * (size - len(poly2)))
inv = [1]
for t in degs[::-1]:
added = t + 1 - len(inv)
tmp = poly_mul(poly2[:t + 1], inv)[len(inv):]
tmp = poly_mul(tmp[:added], inv[:added])
inv.extend([-v for v in tmp[:added]])
return inv
def poly_mul_mod_ntt(poly1, poly2, mod):
p1, p2, p3 = [880803841, 897581057, 998244353]
z1, z2, z3 = [273508579, 872686320, 15311432]
s1 = len(poly1)
s2 = len(poly2)
ntt_size = 2 << ilog2(max(s1, s2) * 2 - 1)
size = s1 + s2 - 1
A = poly1[:] + [0] * (ntt_size - s1)
B = poly2[:] + [0] * (ntt_size - s2)
A1 = _ntt_convolve(A[:], B[:], size, p1, z1)
A2 = _ntt_convolve(A[:], B[:], size, p2, z2)
A3 = _ntt_convolve(A[:], B[:], size, p3, z3)
inv = inv_mod(p1, p2)
for i in range(size):
k = (A2[i] - A1[i]) * inv % p2
A1[i] += k * p1
p12 = p1 * p2
inv = inv_mod(p12, p3)
for i in range(size):
k = (A3[i] - A1[i]) % p3 * inv % p3
A1[i] = (A1[i] + k * (p12 % mod)) % mod
return A1[:size]
def poly_square_mod_ntt(poly1, mod):
p1, p2, p3 = [880803841, 897581057, 998244353]
z1, z2, z3 = [273508579, 872686320, 15311432]
s1 = len(poly1)
ntt_size = 2 << ilog2(s1 * 2 - 1)
size = 2 * s1 - 1
A = poly1[:] + [0] * (ntt_size - s1)
A1 = _ntt_convolve_self(A[:], size, p1, z1)
A2 = _ntt_convolve_self(A[:], size, p2, z2)
A3 = _ntt_convolve_self(A[:], size, p3, z3)
inv = inv_mod(p1, p2)
for i in range(size):
k = (A2[i] - A1[i]) * inv % p2
A1[i] += k * p1
p12 = p1 * p2
inv = inv_mod(p12, p3)
for i in range(size):
k = (A3[i] - A1[i]) % p3 * inv % p3
A1[i] = (A1[i] + k * (p12 % mod)) % mod
return A1[:size]
def poly_mul_mod_builtin(poly1, poly2, mod):
M1, M2, shamt = pack_sequence2_mod(poly1, poly2, mod)
size = len(poly1) + len(poly2) - 1
seq = unpack_sequence(M1 * M2, size, shamt)
return [int(x % mod) for x in seq]
def poly_square_mod_builtin(poly, mod):
M, shamt = pack_sequence_mod(poly, mod)
size = len(poly) * 2 - 1
seq = unpack_sequence(M ** 2, size, shamt)
return [int(x % mod) for x in seq]
def poly_add_mod(poly1, ofs1, poly2, ofs2, size, mod):
diff = ofs2 - ofs1
for i in range(ofs1, ofs1 + size):
poly1[i] = (poly1[i] + poly2[i + diff]) % mod
def poly_sub_mod(poly1, ofs1, poly2, ofs2, size, mod):
diff = ofs2 - ofs1
for i in range(ofs1, ofs1 + size):
poly1[i] = (poly1[i] - poly2[i + diff]) % mod
def poly_mul_mod_karatsuba(poly1, poly2, mod, threshold=128):
size = len(poly1)
if size >= threshold:
size_l = (size + 1) // 2
size_h = size - size_l
p1 = poly_mul_mod_karatsuba(poly1[:size_h], poly2[:size_h], mod, threshold)
p2 = poly_mul_mod_karatsuba(poly1[size_h:], poly2[size_h:], mod, threshold)
q1 = poly1[size_h:]
q2 = poly2[size_h:]
ofs = size_l - size_h
poly_add_mod(q1, ofs, poly1, 0, size_h, mod)
poly_add_mod(q2, ofs, poly2, 0, size_h, mod)
p3 = poly_mul_mod_karatsuba(q1, q2, mod, threshold)
ret = p1
ret.extend([0])
ret.extend(p2)
poly_sub_mod(p3, 0, ret, 2 * size_h, size_l * 2 - 1, mod)
poly_sub_mod(p3, ofs * 2, ret, 0, size_h * 2 - 1, mod)
ofs = 2 * size - 3 * size_l
poly_add_mod(ret, ofs, p3, 0, size_l * 2 - 1, mod)
return ret
else:
return _poly_mul_mod(poly1, poly2, mod)
def _poly_mul_mod(poly1, poly2, mod):
ret = [0] * (len(poly1) + len(poly2) - 1)
for i in range(len(poly2)):
if poly2[i] == 0:
continue
coef = poly2[i]
for j in range(len(poly1)):
ret[i + j] = (ret[i + j] + coef * poly1[j]) % mod
return ret
def poly_mul_mod(poly1, poly2, mod, threshold=128, ntt_threshold=65536):
size1 = len(poly1)
size2 = len(poly2)
if size1 >= ntt_threshold and size2 >= ntt_threshold and mod <= 2 * 10 ** 9:
return poly_mul_mod_ntt(poly1, poly2, mod)
else:
if size1 <= threshold and size2 <= threshold:
return _poly_mul_mod(poly1, poly2, mod)
else:
return poly_mul_mod_builtin(poly1, poly2, mod)
def _poly_square_mod(poly, mod):
size = len(poly)
ret = [0] * (size * 2 - 1)
for i in range(size):
ret[2 * i] = poly[i] * poly[i] % mod
for i in range(size):
coef = 2 * poly[i]
for j in range(i + 1, size):
ret[i + j] = (ret[i + j] + coef * poly[j]) % mod
return ret
def poly_square_mod_karatsuba(poly, mod, threshold=64):
size = len(poly)
if size >= threshold:
size_l = (size + 1) // 2
size_h = size - size_l
p1 = poly_square_mod_karatsuba(poly[:size_h], mod, threshold)
p2 = poly_square_mod_karatsuba(poly[size_h:], mod, threshold)
S = poly[size_h:]
ofs = size_l - size_h
poly_add_mod(S, ofs, poly, 0, size_h, mod)
p3 = poly_square_mod_karatsuba(S, mod, threshold)
ret = p1
ret.extend([0])
ret.extend(p2)
poly_sub_mod(p3, 0, ret, 2 * size_h, size_l * 2 - 1, mod)
poly_sub_mod(p3, ofs * 2, ret, 0, size_h * 2 - 1, mod)
ofs = 2 * size - 3 * size_l
poly_add_mod(ret, ofs, p3, 0, size_l * 2 - 1, mod)
return ret
else:
return _poly_square_mod(poly, mod)
def poly_square_mod(poly, mod, threshold=128, k_threshold=64, ntt_threshold=65536):
size = len(poly)
if size >= ntt_threshold and mod <= 2 * 10 ** 9:
return poly_square_mod_ntt(poly, mod)
elif size >= threshold:
return poly_square_mod_builtin(poly, mod)
elif size >= k_threshold:
return poly_square_mod_karatsuba(poly, mod)
else:
return _poly_square_mod(poly, mod)
def poly_pow_mod(poly, e, mod):
ret = [1]
if e == 0:
return ret
mask = 1 << (e.bit_length() - 1)
ret = [1]
while mask:
if e & mask:
ret = poly_mul_mod(ret, poly, mod)
mask >>= 1
if not mask:
break
ret = poly_square_mod(ret, mod)
return ret
def _poly_rem_mod(poly1, poly2, mod):
if len(poly1) < len(poly2):
return poly1[:]
ret = poly1[:]
dif = len(poly1) - len(poly2) + 1
assert(poly2[0] == 1)
for i in range(dif):
if ret[i] == 0:
continue
coef = ret[i] % mod
for j in range(1, len(poly2)):
ret[i + j] = (ret[i + j] - coef * poly2[j]) % mod
ret[i] = coef
return ret[dif:]
def poly_inverse_mod(poly, size, mod):
assert(poly[0] == 1)
degs = []
deg = size - 1
while deg:
degs.append(deg)
deg >>= 1
poly2 = poly[:]
if len(poly2) < size:
poly2.extend([0] * (size - len(poly2)))
inv = [1]
for t in degs[::-1]:
added = t + 1 - len(inv)
tmp = poly_mul_mod(poly2[:t + 1], inv, mod)[len(inv):]
tmp = poly_mul_mod(tmp[:added], inv[:added], mod)
inv.extend([-v % mod for v in tmp[:added]])
return inv
def poly_div_mod(poly1, poly2, mod, inverse=[]):
assert(len(poly1) >= len(poly2))
assert(poly2[0] == 1)
needed_size = len(poly1) - len(poly2) + 1
if len(inverse) == 0:
inverse = poly_inverse_mod(poly2, needed_size, mod)
assert(len(inverse) >= needed_size)
ret = poly_mul_mod(poly1[:needed_size], inverse[:needed_size], mod)
return ret[:needed_size]
def poly_rem_mod(poly1, poly2, mod, inverse=[]):
size1 = len(poly1)
size2 = len(poly2)
if size1 < size2:
return poly1[:]
needed_size = size1 - size2 + 1
if len(poly2) < 10 or needed_size < 10:
return _poly_rem_mod(poly1, poly2, mod)
if len(inverse) == 0:
inverse = poly_inverse_mod(poly2, needed_size, mod)
poly_q = poly_div_mod(poly1, poly2, mod, inverse)
poly_q2 = poly_mul_mod(poly_q, poly2, mod)
return [(poly1[i] - poly_q2[i]) % mod for i in range(size1 - size2 + 1, size1)]
def poly_normalize(poly):
idx = 0
size = len(poly)
while idx < size and poly[idx] == 0:
idx += 1
return poly[idx:]
def poly_normalize_prime(poly, p):
poly = poly_normalize(poly)
if len(poly) == 0:
return []
inv = inv_mod(poly[0], p)
return [c * inv % p for c in poly]
def poly_gcd_prime(poly1, poly2, p):
while sum(poly2) != 0:
poly1, poly2 = poly2, poly_normalize_prime(poly_rem_mod(poly1, poly2, p), p)
return poly1
def poly_power_rem_mod(e, poly_divisor, mod, threshold=32):
"""
Return x^e % poly_divisor (modulo mod)
assume:
- deg(poly_divisor) > 0
- mod > 1
"""
if e == 0:
return [1]
ret = [1]
mask = 1 << (e.bit_length() - 1)
inverse = []
if len(poly_divisor) >= threshold:
inverse = poly_inverse_mod(poly_divisor, len(poly_divisor), mod)
while mask:
if e & mask:
ret.append(0)
mask >>= 1
if not mask:
break
ret = poly_square_mod(ret, mod)
ret = poly_rem_mod(ret, poly_divisor, mod, inverse)
if len(ret) >= len(poly_divisor):
ret = poly_rem_mod(ret, poly_divisor, mod, inverse)
return ret
def hessenbergize(mat_in, mod):
def mat_swap(mat, i, j):
mat[i], mat[j] = mat[j], mat[i]
for k in range(len(mat)):
mat[k][i], mat[k][j] = mat[k][j], mat[k][i]
def mat_eliminate(mat, col, i, j, u, mod):
n = len(mat)
for k in range(col, n):
mat[j][k] = (mat[j][k] - u * mat[i][k]) % mod
for k in range(n):
mat[k][i] = (mat[k][i] + u * mat[k][j]) % mod
mat = [vec[:] for vec in mat_in]
n = len(mat)
for i in range(n - 2):
g = gcd(mat[i + 1][i], mod)
if g > 1:
g = mat[i + 1][i]
min_value = mod if g == 0 else g
min_row = i + 1
for j in range(i + 2, n):
m_ji = mat[j][i]
g2 = gcd(m_ji, mod)
if g2 == 1:
mat_swap(mat, i + 1, j)
g = 1
break
g = gcd(g, m_ji)
if m_ji > 0 and m_ji < min_value:
min_value, min_row = m_ji, j
else:
if g == 0:
continue
if min_value > g:
for k in range(i + 1, n):
row = k
g2 = gcd(min_value, mat[row][i])
while min_value > g2:
q, min_value = divmod(mat[row][i], min_value)
mat_eliminate(mat, i, min_row, row, q, mod)
min_row, row = row, min_row
if min_value == g:
break
else:
assert(0)
if min_row != i + 1:
mat_swap(mat, min_row, i + 1)
inv = inv_mod(mat[i + 1][i] // g, mod)
for j in range(i + 2, n):
if mat[j][i] == 0:
continue
q = (mat[j][i] // g) * inv % mod
mat_eliminate(mat, i, i + 1, j, q, mod)
return mat
def characteristic_polynomial_mod(mat, mod):
mat = hessenbergize(mat, mod)
n = len(mat)
poly = [0] * (n + 1)
poly[0] = 1
polys = []
polys.append(poly[:])
for i in range(n):
coef = mat[i][i]
for k in range(i + 1, 0, -1):
poly[k] = (poly[k] - coef * poly[k-1]) % mod
t = 1
for j in range(i):
deg_poly = i - j - 1
t = t * mat[deg_poly + 1][deg_poly] % mod
if t == 0:
break
coef = mat[deg_poly][i] * t % mod
if coef == 0:
continue
poly2 = polys[deg_poly]
beg = i + 1 - deg_poly
for l in range(beg, i + 2):
poly[l] = (poly[l] - coef * poly2[l - beg]) % mod
polys.append(poly[:])
return poly
def characteristic_polynomial(mat, ntrial=3, primes=LARGE_PRIMES):
size = len(mat) + 1
ret = [0] * size
t = 0
prod = 1
for p in primes:
char_poly = characteristic_polynomial_mod(mat, p)
inv = inv_mod(prod % p, p)
nret = ret[:]
for i in range(size):
nret[i] += (char_poly[i] - nret[i] % p) * inv % p * prod
nprod = prod * p
for i in range(size):
if nret[i] != ret[i] and nprod - nret[i] != prod - ret[i]:
t = 0
break
else:
t += 1
if t >= ntrial:
return [ret[i] if ret[i] == nret[i] else -(prod - ret[i]) for i in range(size)]
ret = nret
prod = nprod
def mat_mul_vec_mod(mat, vec, mod):
rows = len(mat)
cols = len(mat[0])
ret = [0] * rows
for r in range(rows):
v1 = mat[r]
s = 0
for c in range(cols):
s = (s + v1[c] * vec[c]) % mod
ret[r] = s % mod
return ret
def mat_to_sparse_mat(mat):
ret = [[] for _ in range(len(mat))]
for r in range(len(mat)):
vec = mat[r]
for c in range(len(vec)):
if vec[c]:
ret[r].append(c)
return ret
def mat_mul_sparse_vec_mod(mat, sparse_mat, vec, mod):
ret = [0] * len(vec)
for r in range(len(mat)):
s = 0
for c in sparse_mat[r]:
s = (s + mat[r][c] * vec[c]) % mod
ret[r] = s
return ret
def fast_mat_exp_vec_old(mat, vec, e, mod, sparse=False, char_poly=[]):
"""
- calculate M^e v modulo prime.
- O(n^3 + n * log(n) * log(e))
"""
if e >= len(mat):
if len(char_poly) == 0:
char_poly = characteristic_polynomial_mod(mat, mod) # O(n^3)
poly_rem = poly_power_rem_mod(e, char_poly, mod) # O(n log(n) log(e))
else:
poly_rem = [1] + [0] * e
poly_rem = poly_rem[::-1]
ret_vec = [0] * len(vec)
if sparse:
# O(n^3)
sparse_mat = mat_to_sparse_mat(mat)
for i in range(len(poly_rem)):
coef = poly_rem[i]
if coef != 0:
for k in range(len(vec)):
ret_vec[k] = (ret_vec[k] + coef * vec[k]) % mod
vec = mat_mul_sparse_vec_mod(mat, sparse_mat, vec, mod)
else:
# O(n^3)
for i in range(len(poly_rem)):
coef = poly_rem[i]
if coef != 0:
for k in range(len(vec)):
ret_vec[k] = (ret_vec[k] + coef * vec[k]) % mod
vec = mat_mul_vec_mod(mat, vec, mod)
return ret_vec
def solve_linear_equations_mod(mat, mod):
def mat_swap(mat, i, j):
mat[i], mat[j] = mat[j], mat[i]
def mat_eliminate(mat, col, i, j, u, mod):
n = len(mat[0])
for k in range(col, n):
mat[j][k] = (mat[j][k] - u * mat[i][k]) % mod
m = len(mat)
n = m + 1
for i in range(m):
g = gcd(mat[i][i], mod)
if g > 1:
g = mat[i][i]
min_value = mod if g == 0 else g
min_row = i
for j in range(i + 1, m):
m_ji = mat[j][i]
g2 = gcd(m_ji, mod)
if g2 == 1:
mat_swap(mat, i, j)
g = 1
break
g = gcd(g, m_ji)
if m_ji > 0 and m_ji < min_value:
min_value, min_row = m_ji, j
else:
if g == 0:
continue
if min_value > g:
for k in range(i, m):
row = k
g2 = gcd(min_value, mat[row][i])
while min_value > g2:
q, min_value = divmod(mat[row][i], min_value)
mat_eliminate(mat, i, min_row, row, q, mod)
min_row, row = row, min_row
if min_value == g:
break
else:
assert(0)
if min_row != i:
mat_swap(mat, min_row, i)
inv = inv_mod(mat[i][i] // g, mod)
for j in range(i + 1, m):
if mat[j][i] == 0:
continue
q = (mat[j][i] // g) * inv % mod
mat_eliminate(mat, i, i, j, q, mod)
ret = [mat[i][m] for i in range(m)]
for i in range(m - 1, -1, -1):
if mat[i][i] == 0:
continue
g = gcd(mat[i][i], gcd(ret[i], mod))
if g > 1:
ret[i] //= g
inv = inv_mod(mat[i][i] // g, mod // g)
else:
inv = inv_mod(mat[i][i], mod)
ret[i] = ret[i] * inv % mod
inv = ret[i]
if inv > 0:
inv = mod - inv
for j in range(i):
ret[j] = (ret[j] + mat[j][i] * inv) % mod
ret = [1] + [mod - c if c > 0 else 0 for c in ret[::-1]]
return ret
def fast_mat_exp_vec(mat, vec, e, mod, sparse=False, char_poly=[]):
"""
- calculate M^e v modulo prime.
- O(n^3 + n * log(n) * log(e))
"""
def calc_Ax(mat, vec, e, mod, sparse):
vecs = [vec[:]]
if sparse:
sparse_mat = mat_to_sparse_mat(mat)
for i in range(1, min(e, n) + 1):
vec = mat_mul_sparse_vec_mod(mat, sparse_mat, vec, mod)
vecs.append(vec[:])
else:
for i in range(1, min(e, n) + 1):
vec = mat_mul_vec_mod(mat, vec, mod)
vecs.append(vec[:])
return vecs
n = len(mat)
vecs = calc_Ax(mat, vec, e, mod, sparse)
if e <= n:
return vecs[e]
if max(vecs[0]) == 0:
return vecs[0]
if len(char_poly) == 0:
mat = [[0] * (n + 1) for _ in range(n)]
for i in range(n):
for j in range(n + 1):
mat[i][j] = vecs[j][i]
poly = solve_linear_equations_mod(mat, mod)
else:
poly = char_poly
poly_rem = poly_power_rem_mod(e, poly, mod)[::-1]
ret = [0] * n
for i in range(len(poly_rem)):
coef = poly_rem[i]
vec = vecs[i]
if coef == 0:
continue
for k in range(len(vec)):
ret[k] = (ret[k] + coef * vec[k]) % mod
return ret
def nth_term_of_linear_recurrence(n, char_poly, initial_terms, mod):
"""
O(k * log(k) * log(n))
initial_terms: [a_0, a_1, ..., ]
"""
size = len(initial_terms)
if n < size:
return initial_terms[n]
assert(len(char_poly) == size + 1)
poly_rem = poly_power_rem_mod(n, char_poly, mod)[::-1]
ret = 0
for i in range(size):
ret = (ret + poly_rem[i] * initial_terms[i]) % mod
return ret
def pat(dice, P):
mx = dice[-1] * P
dp = [[0] * (mx + 1) for _ in range(P + 1)]
dp[0][0] = 1
maxs = [0] * (P + 1)
for d_ in dice:
ndp = [d[:] for d in dp]
for t in range(P, 0, -1):
td = t * d_
for pt in range(0, P - t + 1):
for i in range(0, maxs[pt] + 1):
ndp[t + pt][i + td] += dp[pt][i]
maxs[t + pt] = maxs[pt] + td
dp = ndp
return dp[-1]
def ilog2(n):
if n <= 0:
return 0
else:
return n.bit_length() - 1
import sys
def solve():
N, P, C = map(int, sys.stdin.readline().split())
Ps = [2, 3, 5, 7, 11, 13]
Cs = [4, 6, 8, 9, 10, 12]
Ps = pat(Ps, P)
Cs = pat(Cs, C)
poly = poly_mul(Ps, Cs)
mod = 10 ** 9 + 7
for i in range(1, len(poly)):
poly[i] = -poly[i] % mod
poly[0] = 1
Max = 13 * P + 12 * C
inv = poly_inverse_mod(poly, Max, mod)
E = max(0, N - Max)
poly_rem = poly_power_rem_mod(E, poly, mod)
sums = [0] * len(poly)
for i in range(1, len(poly)):
sums[i] = (sums[i-1] + -poly[i]) % mod
ans = 0
for e in range(E, N):
total = 0
for i in range(len(poly_rem)):
total = (total + poly_rem[-1 - i] * inv[i]) % mod
ans = (ans + total * (sums[Max] - sums[N - e - 1])) % mod
poly_rem.extend([0])
poly_rem = poly_rem_mod(poly_rem, poly, mod)
print(ans)
solve()