BZPRO
#5501. 散步
内存限制：512 MiB
时间限制：100 Sec
提交
提交记录
讨论
题目描述
HAHAHA在一个n个点m条边的图上散步，开始时他在1号点，每过一秒他可以走向一个相邻的点，或是在这一秒停下来休息，或是结束这次散步。
问T秒时间内，HAHAHA有多少种不同的散步方案？
输入格式
第一行两个数n,m，表示图中点数和边数。
接下来m行，每行两个数x,y表示x,y之间有一条双向边。
接下来一行一个01字符串，表示T的每一位二进制位（从低位到高位）。
1 <= n <= 3000 , 1<= m <= 5000 , 1<= T <= 2^{100}。
数据保证没有重边或自环。
输出格式
输出一行，表示不同的散步方案（答案模998244353）。
样例
样例输入
4 5
1 2
2 3
3 4
1 4
2 4
11
样例输出
54
数据范围与提示
BZPRO