Winter is coming, and the FIS Ski World Cup is in full swing. Athletes will participate in several races throughout the season to earn points and qualify for the Olympics. As a loyal fan of the ski competitions, Little Z does not want to miss a single race.

In Little Z's world, the World Cup format is quite different from reality: there are $m$ race days in the season, with $m$ races held sequentially. There are $n$ athletes participating. The $i$-th athlete already has $w_i$ points from previous seasons. Due to health reasons, they arrive at the competition venue on day $l_i$ and leave on day $r_i$, participating in all races from $l_i$ to $r_i$. If at least one athlete participates in a race, a competition is held among those present, and a single winner is chosen, who receives $1$ point.

Specifically, to ensure fairness and prevent some athletes from participating in too many races, for any two athletes $i$ and $j$, if $i$ arrives before $j$, they cannot leave later than $j$. That is, for all $1 \le i, j \le n$, if $l_i < l_j$, then $r_i \le r_j$.

Unfortunately, Little Z's favorite athlete, UFT, will miss all races this season due to health reasons (UFT is not counted among the $n$ athletes; consider there to be $n+1$ athletes in total for ranking purposes). Little Z wants to know if there is any theoretical possibility for UFT to qualify for the Olympics. UFT has $v$ points from previous seasons. Since the number of Olympic spots is uncertain, Little Z asks you to find the highest possible rank for UFT among all possible final point distributions (a player's rank is defined as the number of players with more points than them $+1$). Let this minimum rank be $mn$. You need to output the value of $n+1-mn$ (i.e., the number of athletes whose final score is not higher than $v$). Since historical performance is considered when points are equal, Little Z also wants to know: among all possible final point distributions where UFT's rank is $mn$, how many different sets of athletes have a final score not higher than UFT's score? The answer should be modulo $10^9+7$.

Input

The first line contains four integers $n, m, v, tp$. $n, m, v$ are as described above, and $tp$ is the query type, where $tp \in \{0, 1\}$. If $tp=0$, you only need to output the answer to the first question. If $tp=1$, you need to output the answers to both questions.

The next $n$ lines each contain three positive integers $w_i, l_i, r_i$.

Output

Output one or two integers separated by a space, representing the answer(s).

Examples

Input 1

7 7 2 1
1 1 1
1 2 3
2 3 4
1 4 4
2 4 5
1 5 6
2 5 7

Output 1

5 2

Note

Possibility 1: The race winners are $1, 2, 3, 3, 7, 7, 7$ respectively. Athletes $1, 2, 4, 5, 6$ have scores $\le 2$.

Possibility 2: The race winners are $1, 2, 2, 4, 7, 7, 7$ respectively. Athletes $1, 3, 4, 5, 6$ have scores $\le 2$.

Constraints

For all test data, $1 \le n, m \le 2 \times 10^5$, $0 \le w_i, v \le 1 \times 10^9$, $1 \le l_i \le r_i \le m$, $0 \le tp \le 1$. Additionally, for all $1 \le i, j \le n, i \neq j$, if $l_i < l_j$, then $r_i \le r_j$.

Subtask 1 ($5\%$): $n, m \le 8$. Subtask 2 ($5\%$): $n, m \le 15$. Subtask 3 ($20\%$): $n, m \le 20$. Subtask 4 ($10\%$): $n, m \le 2000, tp=0$. Subtask 5 ($20\%$): $tp=0$. Subtask 6 ($20\%$): $n, m \le 2000$. Subtask 7 ($20\%$): No special restrictions.