该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

2026 年的新年钟声即将敲响，银装素裹的长街上挂满了各式各样的红灯笼。

作为新年庆典的总策划，黑大帅希望这场灯会能展现出一种独特的“数学美”。它不想让灯笼孤立地发光，而是设计了一种奇妙的传导机制：每一个灯笼燃烧产生的热量，不仅照亮自己，还会通过特殊的导管，单向传递给另一个特定的灯笼，汇聚成更耀眼的光芒。

“真正的年味，在于万家灯火的连接。”

为了检验这套系统的稳定性，黑大帅记录了若干个关键位置灯笼的“总亮度”。现在，它想知道在总燃料有限的情况下，有多少种初始的点火方案，能够恰好达成眼前这般绚烂的景象。

题目描述

长街上共有 $n$ 盏灯笼，编号为 $1$ 到 $n$。 每盏灯笼 $i$ 初始会装填 $a_{i}$ 单位的燃料（$a_{i}$ 为非负整数）。

灯笼之间的能量传递遵循 “二进制共鸣定律”： 定义函数 $g\left(x\right)$ 为 $x$ 在二进制表示下最低位的$1$ 所代表的数值（即 $x$ 的所有因子中最大的$2$ 的整数次幂）。 例如：$g\left(6\right)=g\left(110_{2}\right)=2$， $g\left(12\right)=g\left(1100_{2}\right)=4$。

能量传递规则如下： 编号为 $i$ 的灯笼，会将自身产生的所有能量（包括初始燃料产生的能量，以及从其他灯笼接收到的能量）单向传递给编号为 $i+g\left(i\right)$ 的灯笼。 如果 $i+g\left(i\right)>n$，则这部分能量会溢出长街，不再被任何灯笼接收（但仍计入总消耗）。

我们定义灯笼 $u$ 的最终亮度 $S_{u}$ 为：所有能通过传递路径流向 $u$ 的灯笼（含 $u$ 自身）的初始燃料 $a$ 之和。

现在的已知信息如下：

1. 所有 $n$ 盏灯笼的初始燃料之和 $\sum_{i=1}^{n} a_{i}$ 恰好为 $K$。
2. 观测到了 $m$ 盏关键灯笼的最终亮度，即给出了 $m$ 对 $\left(u_{j},w_{j}\right)$，表示 $S_{u_{j}}=w_{j}$。

请你计算，有多少种不同的初始燃料序列 $A=\left[a_{1},a_{2},\dots ,a_{n}\right]$，满足上述所有条件？ 答案可能很大，请输出对 $998244353$ 取模的结果。若不存在任何满足条件的方案，输出 $0$。

输入格式

第一行包含三个整数 $n,m,K$，分别表示灯笼的数量、观测记录的数量、以及总燃料限制。

接下来 $m$ 行，每行包含两个整数 $u,w$，表示观测到灯笼 $u$ 的最终亮度 $S_{u}$ 为 $w$。

数据保证不会对同一个灯笼进行重复观测。

输出格式

输出一行一个整数，表示满足条件的方案数。

5 1 10
4 6

84

数据范围

对于 $10\%$ 的测试数据，满足 $n\le 10,K\le 10$。

对于另 $20\%$ 的测试数据，满足 $n\le 1000,K\le 2000$。

对于 $100\%$ 的测试数据，满足 $1\le n\le 2\times 10^{5}$，$1\le m\le n$，$0\le K\le 10^{18}$，$0\le w\le K$。