結果
問題 | 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()