結果
問題 | No.214 素数サイコロと合成数サイコロ (3-Medium) |
ユーザー |
![]() |
提出日時 | 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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 3 |
ソースコード
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) - 1return [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:continuecoef = poly2[i]for j in range(len(poly1)):ret[i + j] += coef * poly1[j]return retdef poly_mul_karatsuba(poly1, poly2, threshold=16):size = len(poly1)if size >= threshold:size_l = (size + 1) // 2size_h = size - size_lp1 = 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_hfor i in range(size_h):q1[ofs + i] += poly1[i]q2[ofs + i] += poly2[i]p3 = poly_mul_karatsuba(q1, q2, threshold)ret = p1ret.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_lfor i in range(size_l * 2 - 1):ret[ofs + i] += p3[i]return retelse: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 = npacksize = (size + 1) >> 1shamt <<= 1return pack[0]def _pack1(seq, shamt):M = _pack(seq, shamt)size = len(seq) * 2 - 1block_size = 1 << ilog2(size - 1)return M, shamt * block_sizedef _pack2(seq1, seq2, shamt):M1 = _pack(seq1, shamt)M2 = _pack(seq2, shamt)size = len(seq1) + len(seq2) - 1block_size = 1 << ilog2(size - 1)return M1, M2, shamt * block_sizedef 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 * sizeshamt = 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 * sizeshamt = max_value.bit_length()return _pack2(seq1, seq2, shamt)def unpack_sequence(M, size, shamt):needed_sizes = []s = sizewhile s > 1:needed_sizes.append(s)s = (s + 1) >> 1ret = [M]for needed_size in needed_sizes[::-1]:mask = (1 << shamt) - 1nret = []for c in ret:nret.append(c & mask)nret.append(c >> shamt)ret = nret[:needed_size]shamt >>= 1return retdef poly_mul_builtin(poly1, poly2):M1, M2, shamt = pack_sequence2(poly1, poly2)size = len(poly1) + len(poly2) - 1return 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 - 1return 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 retdef poly_square_karatsuba(poly, threshold=16):size = len(poly)if size >= threshold:size_l = (size + 1) // 2size_h = size - size_lp1 = poly_square_karatsuba(poly[:size_h], threshold)p2 = poly_square_karatsuba(poly[size_h:], threshold)S = poly[size_h:]ofs = size_l - size_hfor i in range(size_h):S[ofs + i] += poly[i]p3 = poly_square_karatsuba(S, threshold)ret = p1ret.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_lfor i in range(size_l * 2 - 1):ret[ofs + i] += p3[i]return retelse: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 retmask = 1 << (e.bit_length() - 1)ret = [1]while mask:if e & mask:ret = poly_mul(ret, poly, threshold, False)mask >>= 1if not mask:breakret = poly_square(ret, threshold, False)return retdef poly_inverse(poly, size):assert(poly[0] == 1)degs = []deg = size - 1while deg:degs.append(deg)deg >>= 1poly2 = 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 invdef 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 - 1A = 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 % p2A1[i] += k * p1p12 = p1 * p2inv = inv_mod(p12, p3)for i in range(size):k = (A3[i] - A1[i]) % p3 * inv % p3A1[i] = (A1[i] + k * (p12 % mod)) % modreturn 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 - 1A = 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 % p2A1[i] += k * p1p12 = p1 * p2inv = inv_mod(p12, p3)for i in range(size):k = (A3[i] - A1[i]) % p3 * inv % p3A1[i] = (A1[i] + k * (p12 % mod)) % modreturn A1[:size]def poly_mul_mod_builtin(poly1, poly2, mod):M1, M2, shamt = pack_sequence2_mod(poly1, poly2, mod)size = len(poly1) + len(poly2) - 1seq = 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 - 1seq = 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 - ofs1for i in range(ofs1, ofs1 + size):poly1[i] = (poly1[i] + poly2[i + diff]) % moddef poly_sub_mod(poly1, ofs1, poly2, ofs2, size, mod):diff = ofs2 - ofs1for i in range(ofs1, ofs1 + size):poly1[i] = (poly1[i] - poly2[i + diff]) % moddef poly_mul_mod_karatsuba(poly1, poly2, mod, threshold=128):size = len(poly1)if size >= threshold:size_l = (size + 1) // 2size_h = size - size_lp1 = 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_hpoly_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 = p1ret.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_lpoly_add_mod(ret, ofs, p3, 0, size_l * 2 - 1, mod)return retelse: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:continuecoef = poly2[i]for j in range(len(poly1)):ret[i + j] = (ret[i + j] + coef * poly1[j]) % modreturn retdef 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] % modfor i in range(size):coef = 2 * poly[i]for j in range(i + 1, size):ret[i + j] = (ret[i + j] + coef * poly[j]) % modreturn retdef poly_square_mod_karatsuba(poly, mod, threshold=64):size = len(poly)if size >= threshold:size_l = (size + 1) // 2size_h = size - size_lp1 = 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_hpoly_add_mod(S, ofs, poly, 0, size_h, mod)p3 = poly_square_mod_karatsuba(S, mod, threshold)ret = p1ret.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_lpoly_add_mod(ret, ofs, p3, 0, size_l * 2 - 1, mod)return retelse: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 retmask = 1 << (e.bit_length() - 1)ret = [1]while mask:if e & mask:ret = poly_mul_mod(ret, poly, mod)mask >>= 1if not mask:breakret = poly_square_mod(ret, mod)return retdef _poly_rem_mod(poly1, poly2, mod):if len(poly1) < len(poly2):return poly1[:]ret = poly1[:]dif = len(poly1) - len(poly2) + 1assert(poly2[0] == 1)for i in range(dif):if ret[i] == 0:continuecoef = ret[i] % modfor j in range(1, len(poly2)):ret[i + j] = (ret[i + j] - coef * poly2[j]) % modret[i] = coefreturn ret[dif:]def poly_inverse_mod(poly, size, mod):assert(poly[0] == 1)degs = []deg = size - 1while deg:degs.append(deg)deg >>= 1poly2 = 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 invdef poly_div_mod(poly1, poly2, mod, inverse=[]):assert(len(poly1) >= len(poly2))assert(poly2[0] == 1)needed_size = len(poly1) - len(poly2) + 1if 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 + 1if 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 = 0size = len(poly)while idx < size and poly[idx] == 0:idx += 1return 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 poly1def 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 >>= 1if not mask:breakret = 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 retdef 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]) % modfor k in range(n):mat[k][i] = (mat[k][i] + u * mat[k][j]) % modmat = [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 gmin_row = i + 1for 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 = 1breakg = gcd(g, m_ji)if m_ji > 0 and m_ji < min_value:min_value, min_row = m_ji, jelse:if g == 0:continueif min_value > g:for k in range(i + 1, n):row = kg2 = 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_rowif min_value == g:breakelse: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:continueq = (mat[j][i] // g) * inv % modmat_eliminate(mat, i, i + 1, j, q, mod)return matdef characteristic_polynomial_mod(mat, mod):mat = hessenbergize(mat, mod)n = len(mat)poly = [0] * (n + 1)poly[0] = 1polys = []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]) % modt = 1for j in range(i):deg_poly = i - j - 1t = t * mat[deg_poly + 1][deg_poly] % modif t == 0:breakcoef = mat[deg_poly][i] * t % modif coef == 0:continuepoly2 = polys[deg_poly]beg = i + 1 - deg_polyfor l in range(beg, i + 2):poly[l] = (poly[l] - coef * poly2[l - beg]) % modpolys.append(poly[:])return polydef characteristic_polynomial(mat, ntrial=3, primes=LARGE_PRIMES):size = len(mat) + 1ret = [0] * sizet = 0prod = 1for 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 * prodnprod = prod * pfor i in range(size):if nret[i] != ret[i] and nprod - nret[i] != prod - ret[i]:t = 0breakelse:t += 1if t >= ntrial:return [ret[i] if ret[i] == nret[i] else -(prod - ret[i]) for i in range(size)]ret = nretprod = nproddef mat_mul_vec_mod(mat, vec, mod):rows = len(mat)cols = len(mat[0])ret = [0] * rowsfor r in range(rows):v1 = mat[r]s = 0for c in range(cols):s = (s + v1[c] * vec[c]) % modret[r] = s % modreturn retdef 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 retdef mat_mul_sparse_vec_mod(mat, sparse_mat, vec, mod):ret = [0] * len(vec)for r in range(len(mat)):s = 0for c in sparse_mat[r]:s = (s + mat[r][c] * vec[c]) % modret[r] = sreturn retdef 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] * epoly_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]) % modvec = 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]) % modvec = mat_mul_vec_mod(mat, vec, mod)return ret_vecdef 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]) % modm = len(mat)n = m + 1for i in range(m):g = gcd(mat[i][i], mod)if g > 1:g = mat[i][i]min_value = mod if g == 0 else gmin_row = ifor 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 = 1breakg = gcd(g, m_ji)if m_ji > 0 and m_ji < min_value:min_value, min_row = m_ji, jelse:if g == 0:continueif min_value > g:for k in range(i, m):row = kg2 = 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_rowif min_value == g:breakelse: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:continueq = (mat[j][i] // g) * inv % modmat_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:continueg = gcd(mat[i][i], gcd(ret[i], mod))if g > 1:ret[i] //= ginv = inv_mod(mat[i][i] // g, mod // g)else:inv = inv_mod(mat[i][i], mod)ret[i] = ret[i] * inv % modinv = ret[i]if inv > 0:inv = mod - invfor j in range(i):ret[j] = (ret[j] + mat[j][i] * inv) % modret = [1] + [mod - c if c > 0 else 0 for c in ret[::-1]]return retdef 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 vecsn = 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_polypoly_rem = poly_power_rem_mod(e, poly, mod)[::-1]ret = [0] * nfor i in range(len(poly_rem)):coef = poly_rem[i]vec = vecs[i]if coef == 0:continuefor k in range(len(vec)):ret[k] = (ret[k] + coef * vec[k]) % modreturn retdef 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 = 0for i in range(size):ret = (ret + poly_rem[i] * initial_terms[i]) % modreturn retdef pat(dice, P):mx = dice[-1] * Pdp = [[0] * (mx + 1) for _ in range(P + 1)]dp[0][0] = 1maxs = [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] + tddp = ndpreturn dp[-1]def ilog2(n):if n <= 0:return 0else:return n.bit_length() - 1import sysdef 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 + 7for i in range(1, len(poly)):poly[i] = -poly[i] % modpoly[0] = 1Max = 13 * P + 12 * Cinv = 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]) % modans = 0for e in range(E, N):total = 0for i in range(len(poly_rem)):total = (total + poly_rem[-1 - i] * inv[i]) % modans = (ans + total * (sums[Max] - sums[N - e - 1])) % modpoly_rem.extend([0])poly_rem = poly_rem_mod(poly_rem, poly, mod)print(ans)solve()