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()