HAHAHA 的散步

题目描述

HAHAHA 在一个有 n 个点、m 条边的无向图上散步。

开始时，HAHAHA 位于 1 号点。每过一秒，他可以进行以下三种操作之一：

1. 走向一个与当前点相邻的点；
2. 停在原地休息一秒；
3. 结束这次散步。

问在 T 秒时间内，HAHAHA 有多少种不同的散步方案。

答案对 998244353 取模。

输入格式

第一行包含两个整数 n, m，表示图中的点数和边数。

接下来 m 行，每行包含两个整数 x, y，表示点 x 和点 y 之间有一条无向边。

接下来一行包含一个 01 字符串，表示整数 T 的二进制表示。

注意：该二进制串按照 从低位到高位 的顺序给出。

输出格式

输出一行一个整数，表示不同散步方案的数量，结果对 998244353 取模。

数据范围

• 1 <= n <= 3000
• 1 <= m <= 5000
• 1 <= T < 2^100
• 数据保证没有重边或自环。

样例输入

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

样例输出

54

样例说明

二进制串 11 按从低位到高位给出，因此：

T = 1 + 2 = 3

即统计 3 秒以内可以产生的所有不同散步方案数量。