m,k = map(int,input().split())
mod = 10**9+7

def calc(A,B):
    ans = [[0]*m for i in range(m)]
    for i in range(m):
        for j in range(m):
            for t in range(m):
                ans[i][j] += A[i][t]*B[t][j]
                ans[i][j] %= mod
    return ans


A = [[0]*m for i in range(m)]
for i in range(m):
    for j in range(m):
        A[(i+j)%m][j] += 1
        A[(i*j)%m][j] += 1


base = [[0]*m for i in range(m)]
for i in range(m):
    base[i][i] = 1

while k:
    if k & 1:
        base = calc(A,base)
    A = calc(A,A)
    k >>= 1
print(base[0][0])