import numpy as np
import sys

def MI(): return map(int, sys.stdin.readline().split())

def main():
    md=10**9+7
    m,k=MI()
    base=np.zeros((m,m),dtype=np.object)
    for i in range(m):
        for a in range(m):
            j=(a+i)%m
            base[i][j]+=1
            j=(a*i)%m
            base[i][j]+=1

    mat=np.eye(m,dtype=np.object)
    while k:
        if k&1:mat=np.dot(mat,base)%md
        base=np.dot(base,base)%md
        k>>=1
    print(mat[0][0])

main()