P7483 Us 50 Years Later

YSGHYYDS.

YSGH prepared $n$ problems for a contest. The difficulty of problem $i$ is $d_i$, and its value is $c_i$. There are $m$ potential contestants. Contestant $i$ participates in the contest with probability $p_i$. If contestant $i$ participates, then they will solve exactly all problems whose difficulties are between $l_i$ and $r_i$ (including $l_i$ and $r_i$). The contest committee will finally award YSGH a bonus equal to the $k$-th power of the sum of values of all problems that are solved by at least one contestant. In particular, we define $0^0 = 1$. You need to help YSGH compute the expected value of the bonus. Let $P=998244353$. Suppose a rational number $x$ is written in lowest terms as $\frac{a}{b}$. If $\gcd(b,P)=1$, then there exists a unique integer $c$ ($0 \le c < P$) such that $b c \equiv a \pmod{P}$. We call this $c$ the value of $x$ modulo $P$. It can be proven that even if only the value of $p_i$ modulo $P$ is given, the answer still exists uniquely modulo $P$.

The first line contains three integers $n, m, k$, representing the number of problems, the number of potential contestants, and the parameter used to compute the bonus. The next $n$ lines each contain two integers $d_i, c_i$, representing the difficulty and value of problem $i$. The next $m$ lines each contain three integers $l_i, r_i, p_i$, representing the difficulty interval of problems that contestant $i$ can solve, and the probability (given modulo $P$) that they participate in the contest.

Output one line with one integer, representing the expected value of the bonus modulo $P$.

**Sample Explanation \#1** This sample satisfies Special Property A. If the first person participates, they can solve problems $1, 2, 5$. If the second person participates, they can solve problem $3$. So the expected bonus of YSGH is $(412+685+121)\times 2\times (1-3)+544\times (1-2)\times 3+(412+685+121+544)\times 2\times 3\equiv 4068\pmod{P}$. --- **Constraints** **This problem uses bundled testdata.** For $100\%$ of the testdata, $1\le n\le 400$, $0\le k\le 400$, $1\le m\le 10^5$, $1\le d_i\le 10^9$, $1\le l_i\le r_i\le 10^9$, $0\le c_i,p_i < 998244353$. The special constraints and scores of each Subtask are as follows: | Test Package ID | $n\le $ | $k\le $ | Other Constraints | Score | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $400$ | $1$ | Special Property A | $5$ | | $2$ | $400$ | $1$ | None | $6$ | | $3$ | $400$ | $2$ | Special Property A | $7$ | | $4$ | $400$ | $2$ | None | $8$ | | $6$ | $18$ | $100$ | Special Property A | $3$ | | $5$ | $18$ | $100$ | None | $15$ | | $7$ | $100$ | $100$ | Special Property A | $9$ | | $8$ | $100$ | $100$ | None | $16$ | | $9$ | $400$ | $400$ | Special Property A | $10$ | | $10$ | $400$ | $400$ | None | $21$ | Special Property A: For any $1\le i < j\le M$, we have $[l_i,r_i]\cap [l_j,r_j]=\varnothing$. Translated by ChatGPT 5