题目描述
二年九班最近(并非)出现了一种名为吧的风俗。吧是一种相互传阅,创作的文字内容,且每个人只会将吧传递给自己认识的人。现在,吧的管理者为了整顿我们的吧纪,开始规定吧的传阅规则。九班一共有n人,规定吧从s开始传起,经过m次传递,最后到t手上。现给出一个邻接矩阵,表示班中人的认识关系。试求吧的传阅的可能路径的条数。答案对998,244,353取模。
输入
第一行输入四个整数 n,m,s,t。
第二到第n+1行每行输入n个数,其中第i+1行第j个数为表示i和j互相认识,数据保证若a认识b,则必有b认识a,且一个人不认识他自己。
4 3 1 2
0 1 0 0
1 0 1 1
0 1 0 1
0 1 1 0
提示
样例中的3条路径分别为1-2-1-2,1-2-3-2,1-2-4-2。
对20%的数据,n≤5,m≤5。
对50%的数据,n≤10,m≤500。
对100%的数据,n≤100,m≤100000,1≤s,t≤n。