#1414. 阿夸木迷路传

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Shirost

题目描述

给她一个账单,她能买下整个skp。给她一个导航,她能迷路两天两夜。那年她双手插兜,不知道什么是对手。
她就是富可敌国,极端社交恐怖分子的天天发电的江湖人称杨水月的阿夸木。她曾以一手迷惑发言,让整个校队为此震惊。
食肉斯特给她的评价是,当你在群里看到阿夸木秀恩爱时,撤退已经来不及了。就连强如校队顶梁柱毁天灭地的李总统也不能在阿夸木手下活过一秒。
著名的五星上将麦克阿瑟曾这样评价阿夸木,认识人不认识阿夸木,就好像玩游戏不玩原神,上大学不学模电,只能度过一个相对失败的人生,这个世界是属于阿夸木的,阿夸木来允许,阿夸木来承认,阿夸木来背负整个世界。
阿库木究竟是谁,为什么阿夸木有如此大的影响力,敬请收看大型纪录片《阿夸木传奇》。

阿夸木又双叒叕迷路了,这次是在阿夸木家的别墅里。

阿夸木家的别墅有 间房间, 间房间之间有 条无向边相连接。阿夸木的房间在 号结点,她想去的房间在 号结点。

令人震惊的是,阿夸木居然成功走到了她想要去的房间,但是她不知道走了多久,她只知道她恰好走了 条边才到。

现在阿夸木想知道有多少种可能的方案使得阿夸木从自己的房间走到她想去的房间恰好经过了 条边,答案对998244353取模。

形式化的说,求从 号结点走到 号结点恰好经过了 条边有多少种方案,答案对998244353取模。。

输入格式

第一行输入三个正整数

接下来 行输入两个正整数 ,表示从 房间到 房间有一条边。

输出格式

输出一个正整数表示方案数,方案数对 取模。

样例

样例输入

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

样例输出

2

数据范围与提示

,

样例解释

1-2-4 , 1-3-4 一共有两条路径恰好经过两条边