F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 5501. -- 散步

5501: 散步

Time Limit: 100 Sec  Memory Limit: 512 MB
Submit: 11  Solved: 5
[Submit][Status][Discuss]

Description

HAHAHA在一个n个点m条边的图上散步,开始时他在1号点,每过一秒他可以走向一个相邻的点,或是在这一秒停下来休息,或是结束这次散步。
问T秒时间内,HAHAHA有多少种不同的散步方案?

Input

第一行两个数n,m,表示图中点数和边数。
接下来m行,每行两个数x,y表示x,y之间有一条双向边。
接下来一行一个01字符串,表示T的每一位二进制位(从低位到高位)。
1 <= n <= 3000 , 1<= m <= 5000 , 1<= T <= 2^{100}。
数据保证没有重边或自环。

Output

输出一行,表示不同的散步方案(答案模998244353)。

Sample Input

4 5
1 2
2 3
3 4
1 4
2 4
11

Sample Output

54

HINT

Source

鸣谢Hekai提供试题

[Submit][Status][Discuss]

HOME Back