{"raw_statement":[{"iden":"problem statement","content":"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.  \nNext, 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.  \nSupposed 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."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 16$\n*   $1 \\leq M \\leq 10^{18}$\n*   $1 \\leq A_i < 998244353$\n*   $1 \\leq B_i \\leq 10^{17}$\n*   If $i\\neq j$, then $A_i \\neq A_j$.\n*   $M\\leq B_1+B_2+\\cdots B_N$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_N$ $B_N$"},{"iden":"sample input 1","content":"3 3\n3 1\n5 2\n6 3"},{"iden":"sample output 1","content":"819\n\nThere are $6$ possible combinations of $3$ cards.\n\n*   A combination of $1$ card with $3$ written on it, and $2$ cards with $5$ written on them.\n*   A combination of $1$ card with $3$ written on it, $1$ card with $5$ written on it, and $1$ card with $6$ written on it.\n*   A combination of $1$ card with $3$ written on it, and $2$ cards with $6$ written on them.\n*   A combination of $2$ cards with $5$ written on them, and $1$ card with $6$ written on it.\n*   A combination of $1$ card with $5$ written on it, and $2$ cards with $6$ written on them.\n*   A combination of $3$ cards with $6$ written on them.\n\nThe scores are $75$, $90$, $108$, $150$, $180$, and $216$, respectively, for a sum of $819$."},{"iden":"sample input 2","content":"3 2\n1 1\n5 2\n25 1"},{"iden":"sample output 2","content":"180\n\n\"A combination of a card with $1$ and another card with $25$\" and \"a combination of two cards with $5$ written on them\" have the same score of $25$, but they are considered to be different combinations."},{"iden":"sample input 3","content":"10 232657150901347497\n139547946 28316250877914575\n682142538 78223540024979445\n110643588 74859962623690081\n173455495 60713016476190629\n271056265 85335723211047202\n801329567 48049062628894325\n864844366 54979173822804784\n338794337 69587449430302156\n737638908 15812229161735902\n462149872 49993004923078537"},{"iden":"sample output 3","content":"39761306\n\nBe sure to print the answer modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}