Runner's Problem

여러분은 직사각형 들판을 달리고 있다. 이 들판은 3개의 행과 m개의 열을 가진 행렬로 나타낼 수 있다. (i, j)은 i-th번째 행과 j-th번째 열에 속하는 칸을 나타낸다.

(2, 1)에서 출발하여 (2, m)에서 경로를 끝내야 한다. 칸 (i, j)에서는 다음 칸으로 이동할 수 있다.

• (i - 1, j + 1) — i > 1인 경우에만 가능하다.
• (i, j + 1), 또는
• (i + 1, j + 1) — i < 3인 경우에만 가능하다.

하지만 경로를 막는 n개의 장애물이 있다. k-th번째 장애물은 세 정수 ak, lk, rk로 나타내며, lk ≤ j ≤ rk를 만족하는 모든 칸 (ak, j)에 들어가는 것을 금지한다.

(2, 1)에서 (2, m)까지 가는 서로 다른 경로의 수를 계산하고, 이를 109 + 7로 나눈 나머지를 출력해야 한다.

첫 번째 줄에는 두 정수 n와 m (1 ≤ n ≤ 104, 3 ≤ m ≤ 1018)이 주어진다. 각각 장애물의 수와 행렬의 열 수다.

이어서 n개의 줄이 주어지며, 각 줄에는 세 정수 ak, lk, rk (1 ≤ ak ≤ 3, 2 ≤ lk ≤ rk ≤ m - 1)이 주어진다. 이는 lk ≤ j ≤ rk를 만족하는 모든 칸 (ak, j)을 막는 장애물을 나타낸다. 일부 칸은 여러 장애물에 의해 막힐 수 있다.

(2, 1)에서 (2, m)까지 가는 서로 다른 경로의 수를 109 + 7로 나눈 나머지를 출력한다. (2, 1)에서 (2, m)까지 가는 것이 불가능하면 경로의 수는 0이다.