import algorithm, macros, math, sequtils, strutils, tables
# import bitops, lenientops, deques,
#   heapqueue, sets, sugar

let read* = iterator: string =
  while true: (for s in stdin.readLine.split: yield s)

template input*(T: static[typedesc]): untyped = 
  when T is int: read().parseInt
  elif T is float: read().parseFloat
  elif T is string: read()
  elif T is char: read()[0]

macro dump*(args: varargs[typed]): untyped =
  result = newNimNode(nnkStmtList)
  for x in args:
    let s = toStrLit(x)
    result.add quote do: stderr.write `s`, " = ", `x`, " "
  result.add quote do: stderr.write "\n"

proc `|=`*(n: var int, m: int) = n = n or m
proc `|=`*(n: var bool, m: bool) = n = n or m
proc `&=`*(n: var int, m: int) = n = n and m
proc `&=`*(n: var bool, m: bool) = n = n and m
proc `^=`*(n: var int, m: int) = n = n xor m
proc `^=`*(n: var bool, m: bool) = n = n xor m
proc `%=`*(n: var int, m: int) = n = n mod m
proc `/=`*(n: var int, m: int) = n = n div m
proc `<<=`*(n: var int, m: int) = n = n shl m
proc `>>=`*(n: var int, m: int) = n = n shr m
proc `<?=`*(n: var SomeNumber, m: SomeNumber) = n = min(n, m)
proc `>?=`*(n: var SomeNumber, m: SomeNumber) = n = max(n, m)
proc newSeq2*[T](n1, n2: Natural): seq[seq[T]] = newSeqWith(n1, newSeq[T](n2))
proc newSeq3*[T](n1, n2, n3: Natural): seq[seq[seq[T]]] = newSeqWith(n1, newSeqWith(n2, newSeq[T](n3)))
proc newSeq4*[T](n1, n2, n3, n4: Natural): seq[seq[seq[seq[T]]]] = newSeqWith(n1, newSeqWith(n2, newSeqWith(n3, newSeq[T](n4))))

# -------------------------------------------------- #

const modulus = 10 ^ 9 + 7
 
type ModMatrix* = seq[seq[int]]
 
proc initModMatrix*(N: Natural, M: Natural): ModMatrix =
  ModMatrix(newSeqWith(N, newSeq[int](M)))
 
proc initModMatrix*(N: Natural): ModMatrix =
  ModMatrix(newSeqWith(N, newSeq[int](N)))
 
proc initIdentityModMatrix*(N: Natural): ModMatrix =
  var R = initModMatrix(N)
  for i in 0 .. N - 1:
    R[i][i] = 1
  return R
 
proc toModMatrix*(A: seq[seq[int]]): ModMatrix =
  A
 
proc height*(A: ModMatrix): Natural {.inline.} =
  A.len
 
proc width*(A: ModMatrix): Natural {.inline.} =
  A[0].len
 
proc `+`*(A: ModMatrix, B: ModMatrix): ModMatrix =
  #assert height(A) == height(B)
  #assert width(A) == width(B)
  let (N, M) = (height(A), width(A))
  var R = initModMatrix(N, M)
  for i in 0 .. N - 1:
    for j in 0 .. M - 1:
      R[i][j] = A[i][j] + B[i][j]
      if R[i][j] >= modulus:
        R[i][j] -= modulus
  return R
 
proc `-`*(A: ModMatrix, B: ModMatrix): ModMatrix =
  #assert height(A) == height(B)
  #assert width(A) == width(B)
  let (N, M) = (height(A), width(A))
  var R = initModMatrix(N, M)
  for i in 0 .. N - 1:
    for j in 0 .. M - 1:
      R[i][j] = A[i][j] - B[i][j]
      if R[i][j] < 0:
        R[i][j] += modulus
  return R
 
proc `*`*(A: ModMatrix, B: ModMatrix): ModMatrix =
  #assert width(A) == height(B)
  let (N, P, M) = (height(A), width(A), width(B))
  var R = initModMatrix(N, M)
  for i in 0 .. N - 1:
    for j in 0 .. M - 1:
      for k in 0 .. P - 1:
        R[i][j] += A[i][k] * B[k][j]
        R[i][j] = R[i][j] mod modulus
  return R
 
proc `^`*(A: ModMatrix, k: Natural): ModMatrix =
  #assert height(A) == width(A)
  let N = height(A)
  var (A, k, R) = (A, k, initIdentityModMatrix(N))
  while k > 0:
    if bool(k and 1):
      R = R * A
    A = A * A
    k = k shr 1
  return R
 
proc `+=`*(A: var ModMatrix, B: ModMatrix) {.inline.} =
  A = A + B
proc `-=`*(A: var ModMatrix, B: ModMatrix) {.inline.} =
  A = A - B
proc `*=`*(A: var ModMatrix, B: ModMatrix) {.inline.} =
  A = A * B
proc `^=`*(A: var ModMatrix, k: Natural) {.inline.} =
  A = A ^ k

# -------------------------------------------------- #

let M, K = input(int)
var A = initModMatrix(M, M)
for j in 0 .. M - 1:
  for k in 0 .. M - 1:
    A[(j + k) mod M][j] += 1
    A[(j * k) mod M][j] += 1
A ^= K
var B = initModMatrix(M, 1); B[0][0] = 1
let R = A * B
echo R[0][0]