Okabe and El Psy Kongroo

Okabe는 산책을 좋아하지만 Organization의 첩자들이 어디에나 있을 수 있다는 것을 알고 있다. 그래서 그는 자신의 도시에서 안전하게 할 수 있는 서로 다른 산책의 수를 알고 싶어 한다. Okabe의 도시는 x과 y이 음이 아닌 모든 점 (x, y)으로 나타낼 수 있다. Okabe는 원점 (점 (0, 0))에서 출발하여 점 (k, 0)에 도달해야 한다. If Okabe이 현재 점 (x, y)에 있다면, 한 걸음에 (x + 1, y + 1), (x + 1, y), 또는 (x + 1, y - 1)로 이동할 수 있다.

추가로, n개의 수평선분이 있으며, 그중 i-th 선분은 x = ai부터 x = bi까지 양 끝점을 포함하고, y = ci에 놓여 있다. a1 = 0, an ≤ k ≤ bn, 그리고 2 ≤ i ≤ n인 경우 ai = bi - 1임이 보장된다. i-th 선분은 Okabe의 x 값이 ai ≤ x ≤ bi를 만족할 때 y 값이 0 ≤ y ≤ ci 범위에 있도록 강제하며, 그렇지 않으면 첩자에게 발각될 수 있다. 이는 한 선분이 끝나고 다른 선분이 시작하는 지점에서는 두 선분 아래에 있어야 한다는 뜻이기도 하다.

이제 Okabe는 이러한 조건을 만족하며 원점에서 점 (k, 0)까지 가는 산책의 수를 109 + 7로 나눈 나머지를 알고 싶어 한다.

입력의 첫째 줄에는 정수 n와 k (1 ≤ n ≤ 100, 1 ≤ k ≤ 1018)가 주어진다. 이는 선분의 수와 목적지의 x 좌표이다.

다음 n개의 줄에는 공백으로 구분된 세 정수 ai, bi, ci (0 ≤ ai < bi ≤ 1018, 0 ≤ ci ≤ 15)가 주어진다. 이는 선분의 왼쪽 끝과 오른쪽 끝, 그리고 그 y 좌표이다.

a1 = 0, an ≤ k ≤ bn, 그리고 2 ≤ i ≤ n인 경우 ai = bi - 1임이 보장된다.

조건을 만족하는 산책의 수를 1000000007 (109 + 7)로 나눈 나머지를 출력한다.

위 그래프는 예제 1에 해당한다. 가능한 산책은 다음과 같다.

위 그래프는 예제 2에 해당한다. Okabe가 (3, 0)에 도달하는 산책은 단 하나뿐이다. 그 이후 가능한 산책은 다음과 같다.