问题2421--九班的吧

2421: 九班的吧

时间限制: 1 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交] [状态] [讨论版] [命题人:]

题目描述

二年九班最近(并非)出现了一种名为吧的风俗。吧是一种相互传阅,创作的文字内容,且每个人只会将吧传递给自己认识的人。现在,吧的管理者为了整顿我们的吧纪,开始规定吧的传阅规则。九班一共有n人,规定吧从s开始传起,经过m次传递,最后到t手上。现给出一个邻接矩阵,表示班中人的认识关系。试求吧的传阅的可能路径的条数。答案对998,244,353取模。

输入

第一行输入四个整数 n,m,s,t。
第二到第n+1行每行输入n个数,其中第i+1行第j个数为表示i和j互相认识,数据保证若a认识b,则必有b认识a,且一个人不认识他自己。

输出

一行一个数,表示可能的路径条数。

样例输入 Copy

4 3 1 2
0 1 0 0
1 0 1 1
0 1 0 1
0 1 1 0

样例输出 Copy

3

提示

样例中的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。

来源/分类