class Modulo_Matrix(): #入力 def __init__(self,M,Mod): self.ele=[[x%Mod for x in X] for X in M] self.Mod=Mod R=len(M) if R!=0: C=len(M[0]) else: C=0 self.row=R self.col=C self.size=(R,C) #出力 def __str__(self): T="" (r,c)=self.size for i in range(r): U="[" for j in range(c): U+=str(self.ele[i][j])+" " T+=U[:-1]+"]\n" return "["+T[:-1]+"]" #+,- def __pos__(self): return self def __neg__(self): return self.__scale__(-1) #加法 def __add__(self,other): A=self B=other if A.size!=B.size: raise Modulo_Matrix_Error("2つの行列のサイズが異なります.({},{})".format(A.size,B.size)) M=A.ele N=B.ele L=[0]*self.row for i in range(A.row): E,F=M[i],N[i] L[i]=[(E[j]+F[j])%self.Mod for j in range(self.col)] return Modulo_Matrix(L,self.Mod) #減法 def __sub__(self,other): return self+(-other) #乗法 def __mul__(self,other): A=self B=other if isinstance(B,Modulo_Matrix): R=A.row C=B.col if A.col!=B.row: raise Modulo_Matrix_Error("左側の列と右側の行が一致しません.({},{})".format(A.size,B.size)) G=A.col M=A.ele N=B.ele E=[[0]*other.col for _ in range(self.row)] for i in range(R): F=M[i] for j in range(C): for k in range(G): E[i][j]=(E[i][j]+F[k]*N[k][j])%self.Mod return Modulo_Matrix(E,self.Mod) elif isinstance(B,int): return A.__scale__(B) def __rmul__(self,other): if isinstance(other,int): return self*other def Inverse(self): M=self if M.row!=M.col: raise Modulo_Matrix_Error("正方行列ではありません.") R=M.row I=[[1*(i==j) for j in range(R)] for i in range(R)] G=M.Column_Union(Modulo_Matrix(I,self.Mod)) G=G.Row_Reduce() A,B=[None]*R,[None]*R for i in range(R): A[i]=G.ele[i][:R] B[i]=G.ele[i][R:] if A==I: return Modulo_Matrix(B,self.Mod) else: raise Modulo_Matrix_Error("正則ではありません.") #スカラー倍 def __scale__(self,r): M=self.ele L=[[(r*M[i][j])%self.Mod for j in range(self.col)] for i in range(self.row)] return Modulo_Matrix(L,self.Mod) #累乗 def __pow__(self,n): A=self if A.row!=A.col: raise Modulo_Matrix_Error("正方行列ではありません.") if n<0: return (A**(-n)).Inverse() R=Modulo_Matrix([[1*(i==j) for j in range(A.row)] for i in range(A.row)],self.Mod) D=A while n>0: if n%2==1: R*=D D*=D n=n>>1 return R #等号 def __eq__(self,other): A=self B=other if A.size!=B.size: return False for i in range(A.row): for j in range(A.col): if A.ele[i][j]!=B.ele[i][j]: return False return True #不等号 def __neq__(self,other): return not(self==other) #転置 def Transpose(self): self.col,self.row=self.row,self.col self.ele=list(map(list,zip(*self.ele))) #行基本変形 def Row_Reduce(self): M=self (R,C)=M.size T=[] for i in range(R): U=[] for j in range(C): U.append(M.ele[i][j]) T.append(U) I=0 for J in range(C): if T[I][J]==0: for i in range(I+1,R): if T[i][J]!=0: T[i],T[I]=T[I],T[i] break if T[I][J]!=0: u=T[I][J] u_inv=pow(u,self.Mod-2,self.Mod) for j in range(C): T[I][j]*=u_inv T[I][j]%=self.Mod for i in range(R): if i!=I: v=T[i][J] for j in range(C): T[i][j]-=v*T[I][j] T[i][j]%=self.Mod I+=1 if I==R: break return Modulo_Matrix(T,self.Mod) #列基本変形 def Column_Reduce(self): M=self (R,C)=M.size T=[] for i in range(R): U=[] for j in range(C): U.append(M.ele[i][j]) T.append(U) J=0 for I in range(R): if T[I][J]==0: for j in range(J+1,C): if T[I][j]!=0: for k in range(R): T[k][j],T[k][J]=T[k][J],T[k][j] break if T[I][J]!=0: u=T[I][J] u_inv=pow(u,self.Mod-2,self.Mod) for i in range(R): T[i][J]*=u_inv T[i][J]%=self.Mod for j in range(C): if j!=J: v=T[I][j] for i in range(R): T[i][j]-=v*T[i][J] T[i][j]%=self.Mod J+=1 if J==C: break return Modulo_Matrix(T,self.Mod) #行列の階数 def Rank(self): M=self.Row_Reduce() (R,C)=M.size T=M.ele S=0 for i in range(R): f=False for j in range(C): if T[i][j]!=0: f=True break if f: S+=1 else: break return S #行の結合 def Row_Union(self,other): return Modulo_Matrix(self.ele+other.ele,self.Mod) #列の結合 def Column_Union(self,other): E=[] for i in range(self.row): E.append(self.ele[i]+other.ele[i]) return Modulo_Matrix(E,self.Mod) def __getitem__(self,index): assert isinstance(index,tuple) and len(index)==2 return self.ele[index[0]][index[1]] def __setitem__(self,index,val): assert isinstance(index,tuple) and len(index)==2 self.ele[index[0]][index[1]]=val #================================================ M,K=map(int,input().split()) Mod=10**9+7 X=Modulo_Matrix([[1]*M for _ in range(M)],Mod) for i in range(M): for j in range(M): X[(i*j)%M,i]+=1 print(pow(X,K)[0,0])