Chạy qua sân

Một vận động viên chạy qua một sân hình chữ nhật gồm $3$ hàng và $m$ cột. Ô $(i,j)$ là ô nằm ở hàng $i$, cột $j$.

Vận động viên xuất phát tại ô $(2,1)$ và phải kết thúc tại ô $(2,m)$. Từ ô $(i,j)$, anh ta có thể di chuyển tới:

• $(i-1,j+1)$ — chỉ khi $i>1$,
• $(i,j+1)$,
• $(i+1,j+1)$ — chỉ khi $i<3$.

Trên sân có $n$ chướng ngại vật. Chướng ngại vật thứ $k$ được mô tả bởi ba số nguyên $a_k$, $l_k$, $r_k$: cấm đi vào mọi ô $(a_k,j)$ với $l_k\le j\le r_k$. Một ô có thể bị chặn bởi nhiều chướng ngại vật.

Hãy đếm số đường đi khác nhau từ $(2,1)$ đến $(2,m)$, lấy dư theo ${10}^9+7$. Nếu không tồn tại đường đi nào, đáp án là $0$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$ — số chướng ngại vật và số cột của sân.
• $n$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a_k$, $l_k$, $r_k$ mô tả một chướng ngại vật.

Dữ liệu ra

In ra một số nguyên duy nhất — số đường đi từ $(2,1)$ đến $(2,m)$, lấy dư theo ${10}^9+7$.

Ràng buộc

• $1\le n\le {10}^4$
• $3\le m\le {10}^{18}$
• $1\le a_k\le 3$
• $2\le l_k\le r_k\le m-1$

Ví dụ