P=1e9+7;long n,s,x;m,i;long pom(int a,int i){x=i?pom(1L*a*a%P,i/2)*(i%2?a:1)%P:1;}main(t){for(scanf("%ld%d",&n,&m);i