Problem Statement

There are some cards. Each card has one of $N$ integers written on it. Specifically, there are $B_i$ cards with $A_i$ written on them. Next, for a combination of $M$ cards chosen out of these $(B_1+B_2\cdots +B_N)$ cards, we define the score of the combination by the product of the integers written on the $M$ cards. Supposed that cards with the same integer written on them are indistinguishable, find the sum, modulo $998244353$, of the scores over all possible combinations of $M$ cards.

Constraints

• $1 \leq N \leq 16$
• $1 \leq M \leq 10^{18}$
• $1 \leq A_i < 998244353$
• $1 \leq B_i \leq 10^{17}$
• If $i\neq j$, then $A_i \neq A_j$.
• $M\leq B_1+B_2+\cdots B_N$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print the answer.