题面欺诈系列...
因为一个点最多只能连到前k个点，所以只有当前的连续k个点的连通情况是对接下来的求解有用的
那么就可以计算k个点的所有连通情况，dfs以下发现k=5的时候有52种。
我们把它们用类似于并查集的方式表达（比如12132代表点1和点3连通，2和5连通，3自己），然后再压缩一下。
但要注意的是，12132和23213这两种实际对应的是一种连通情况，我们只要把它都化成字典序最小的那种就可以了
然后考虑增加一个新点以后状态的转移，可以枚举这个点与前k个点（始状态S）的连边情况，其中有一些是不合法的：
1.连到了两个本来就连通的点上（导致成环）
2.在1号点不与其他点连通的情况下，没有连到1号点（导致不连通）
然后再根据连边情况得到终状态E，将trans[S][E]++。最后trans[i][j]表示的就是加入一个点后由i状态到j状态的方案数
那么就可以得到递推式$f[i][j]=\sum^{总状态数}_{k=1}{f[i-1][k]*trans[k][j]}$，其中f[i][j]表示以i为结尾的k个点状态是j的方案数
那么答案就是f[N][1]（假设1是都连通的状态）
然后初值就应该是f[K][i]=i状态的方案数，其中i状态的方案数为它其中每个联通块方案数的乘积。
那么联通块的方案数怎么算呢？其实题面已经说了...n个点的方案数就是$n^{n-2)}$
然后就可以愉快地dp一脸啦
容易发现递推的形式其实和矩阵乘法是相同的，把f[i]和trans看作矩阵，就是$f[N]=f[K]*trans^{N-K}$
然后就可以倍增做矩阵快速幂了。方法和整数的快速幂是一样的。
复杂度：
K=5的状态数接近50，$log(10^{15})$接近50。
所以基本上是$50^3*50=6250000$的。
代码写的很蛋疼...
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#define LL long long
#define inf 0x3f3f3f3f
using namespace std;
const LL maxn=1e15+,maxs=,p65=,mod=; LL rd(){
LL x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} LL N;int K,sct,num[]={,,,,,};
LL f[maxs];
LL trans[][maxs][maxs],out[][maxs][maxs];
struct ST{
int s[];
ST(int x=){memset(s,x,sizeof(s));}
}sta[maxs];
struct Mat{
LL m[maxs][maxs];
Mat(){memset(m,,sizeof(m));}
};
int mp[p65]; void print(ST s){
for(int i=;i<=K;i++) printf("%d",s.s[i]);
}
int STtoInt(ST s){
int x=;for(int i=;i<=K;i++) x=x*+s.s[i];return x;
} ST toLeast(ST s){
ST flag=ST(-),re=ST();int n=;
for(int i=;i<=K;i++){
if(flag.s[s.s[i]]==-) flag.s[s.s[i]]=n++;
re.s[i]=flag.s[s.s[i]];
}return re;
} void dfs1(int x,ST s,int m){
if(x>=K+){
sta[++sct]=s;mp[STtoInt(s)]=sct;return;
}
for(int i=;i<=m+;i++){
s.s[x]=i;
dfs1(x+,s,max(m,i));
}
} void dfs2(int x,ST s,ST from){
if(x>=K+){
bool flag[],bb=s.s[];ST to=ST();int mi=;
memset(flag,,sizeof(flag));
//print(from);printf("\t");print(s);printf("\n");
for(int i=;i<=K;i++){
if(!s.s[i]) continue;
if(flag[from.s[i]]) return;
flag[from.s[i]]=;mi=min(mi,from.s[i]);
}
for(int i=;i<=K;i++){
to.s[i-]=flag[from.s[i]]?mi:from.s[i];
if(from.s[]==to.s[i-]) bb=;
}to.s[K]=mi;
if(!bb) return;
to=toLeast(to);
//print(from);printf("\t");print(s);printf("\t");print(to);printf("\n");
trans[][mp[STtoInt(from)]][mp[STtoInt(to)]]++; }else{
dfs2(x+,s,from);s.s[x]=;dfs2(x+,s,from);
}
} void sets(){
for(int i=;i<=sct;i++){
dfs2(,ST(),sta[i]);
//for(int j=1;j<=sct;j++) printf("%d ",trans[0][i][j]);printf("\n");
ST cnt=ST();
for(int j=;j<=K;j++) cnt.s[sta[i].s[j]]++;
f[i]=;for(int j=;j<K;j++) if(num[cnt.s[j]])f[i]*=num[cnt.s[j]];
}
} void solve(){
LL p=N-K;bool b=,c=;int i,j,k;
for(i=;i<=sct;i++) out[][i][i]=;
while(p){
if(p&){
memset(out[c],,sizeof(out[c]));
for(i=;i<=sct;i++){
for(j=;j<=sct;j++){
for(k=;k<=sct;k++){
out[c][i][j]=(out[c][i][j]+out[c^][i][k]*trans[b^][k][j])%mod;
}
}
}c^=;
}
memset(trans[b],,sizeof(trans[b]));
for(i=;i<=sct;i++){
for(j=;j<=sct;j++){
for(k=;k<=sct;k++){
trans[b][i][j]=(trans[b][i][j]+trans[b^][i][k]*trans[b^][k][j])%mod;
}
}
}p>>=;b^=;
}LL ans=;
for(i=;i<=sct;i++){
ans=(ans+f[i]*out[c^][i][])%mod;
}printf("%d\n",ans);
} int main(){
int i,j,k;
K=rd(),N=rd();
dfs1(,ST(),);sets();
solve();
return ;
}