Basketball Performance Failure Degree

There are N special basketballs on the court, among which exactly M are deflated. Thanks to the spectacular skills of Cai Xukun, when he throws a deflated ball it always goes in, and when he throws a ball in normal condition it always misses.

Cai Xukun hosts S tour performances. In the i-th performance, the audience specifies a number k_i indicating how many balls will be thrown. Then, from the N basketballs, exactly n_i balls are chosen and placed on the court such that exactly m_i of them are deflated. Cai Xukun then randomly (uniformly and without replacement) selects k_i balls from these n_i basketballs to shoot. If he scores with x balls (note that a ball scores if and only if it is deflated), the failure degree of that performance is defined as

$$x^L$$

The performances are mutually independent. The audience wants to know the sum of the expected failure degrees of the S performances, modulo 998244353.

The expected failure degree for one performance is computed by the hypergeometric distribution. In the i-th performance, let the probability of scoring exactly x baskets be

$$P(x)=\frac{\binom{m_i}{x}\,\binom{n_i-m_i}{k_i-x}}{\binom{n_i}{k_i}}.$$

Then the expected failure degree is

$$E_i=\sum_{x=0}^{\min\{k_i,\;m_i\}} x^L \cdot P(x).$$

You are to compute the value

$$\sum_{i=1}^{S} E_i \bmod 998244353.$$

inputFormat

The first line contains four integers N, M, L and S:

• N (total number of basketballs),
• M (number of deflated balls among them),
• L (the exponent in the failure degree formula),
• S (number of performances).

Then S lines follow. The i-th of these lines contains three integers ki, ni and mi, which denote that in the i-th performance:

• ni balls are chosen out of the N basketballs, among which exactly mi are deflated,
• Cai Xukun will then randomly choose ki balls to shoot.

You can assume that 0 ≤ m_i ≤ n_i ≤ N and 0 ≤ k_i ≤ n_i.

outputFormat

Output a single integer: the sum of the expected failure degrees for all performances, modulo 998244353.

sample

5 3 2 3
2 3 1
3 5 3
1 2 1

665968546

</p>