Charles is a big fan of minecraft-coins and a wise investor in this kind of currency. He has $$$n$$$ coins to invest, and he decides to invest each one of them separately.
The minecraft-coin market is Bubbaloo, but Charles knows it well: he knows that there are exactly $$$s$$$ possible returns $$$v_1, v_2, \dots, v_s$$$, all distinct from one another, and that a single investment yields the return $$$v_a$$$ with probability $$$p_a$$$. The returns of his $$$n$$$ investments are independent of each other and all follow this same distribution.
Let $$$X$$$ be the sum of the returns of all his investments. For some strange reason, Charles is interested in knowing the expected value of $$$X^k$$$. Please help Charles find out this piece of information.
Since the result may not be an integer, you must report it modulo $$$998244353$$$.
The first line contains three integers $$$s$$$, $$$n$$$ and $$$k$$$ ($$$1 \le s \le 1000$$$, $$$1 \le n \le 10^9$$$, $$$1 \le k \le 10^5$$$): the number of possible returns, the number of coins Charles invests, and the exponent he is interested in.
Each of the next $$$s$$$ lines contains three integers $$$v_a$$$, $$$\alpha_a$$$ and $$$\beta_a$$$ ($$$0 \le v_a \le 10^9$$$, $$$1 \le \alpha_a \le \beta_a \lt 998244353$$$), meaning that a single investment yields the return $$$v_a$$$ with probability $$$p_a = \alpha_a / \beta_a$$$.
It is guaranteed that the values $$$v_a$$$ are pairwise distinct and that $$$\sum_{a=1}^{s} p_a = 1$$$ holds exactly as an identity between rationals.
Print a single integer: the value of $$$E[X^k]$$$ modulo $$$998244353$$$.
It can be shown that $$$E[X^k]$$$ is a rational number whose denominator is not divisible by $$$p = 998244353$$$. Therefore there is a unique integer $$$y$$$ with $$$0 \le y \lt p$$$ such that $$$y \cdot q \equiv r \pmod{p}$$$, where $$$r/q$$$ is $$$E[X^k]$$$ written in lowest terms; you must report that $$$y$$$.
2 1 30 1 22 1 2
4
2 3 20 1 21 1 2
3
2 4 11 1 34 2 3
12
1 1 100000597925701 1 1
666721797
In the first example Charles invests a single coin, whose return is $$$0$$$ or $$$2$$$ with equal probability. Then $$$E[X^3] = \frac{1}{2} \cdot 0 + \frac{1}{2} \cdot 8 = 4$$$.
In the second example each investment yields $$$0$$$ or $$$1$$$ with equal probability, so $$$X$$$ follows a binomial distribution with $$$3$$$ trials and success probability $$$\frac{1}{2}$$$. Hence $$$E[X^2] = \frac{3}{4} + \frac{9}{4} = 3$$$.
In the third example the expected return of a single investment is $$$\frac{1}{3} \cdot 1 + \frac{2}{3} \cdot 4 = 3$$$, and by linearity $$$E[X] = 4 \cdot 3 = 12$$$.
