题目描述

给定 $n$ 个小球，其中第 $i$ 个小球位于数轴的 $x_i$ 处，小球上有数字 $y_i$。

每经过一秒，每个小球都有 $\frac{1}{2}$ 的概率向右移动一步。当任意小球到达位置 $T$ 时，小球会被立刻取走。

如果某一秒，有两个相邻的小球，左边的向右移动且右边的不动，那么两个小球会合并成一个，且合并后小球的数字为合并前的小球数字的乘积。

求所有小球都被取走时的数字之和的期望值，答案对 $998244353$ 取模。

输入格式

输入的第一行包含两个整数 $n, T$，用一个空格分隔。

接下来 $n$ 行，每行包含两个数 $x_i, y_i$，用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

3 5
2 1
3 1
4 1

406692146

提示

样例说明

$\frac{59}{27} \equiv 406692146 \pmod{998244353}$，其中 $\frac{1}{27} \equiv 480636170 \pmod{998244353}$。

评测用例规模与约定

• 对于 $20\%$ 的评测用例，$n \leq 5$，$T \leq 10$；
• 对于 $40\%$ 的评测用例，$n \leq 10$，$T \leq 20$；
• 对于所有评测用例，$1 \leq n < T \leq 100$，$1 \leq x_{i-1} < x_i < T$，$1 \leq y_i \leq 10^9$。