CF954F Runner's Problem

你正在穿越一个矩形田地。这个田地可以表示为一个有 $3$ 行 $m$ 列的矩阵。$(i,j)$ 表示第 $i$ 行第 $j$ 列的一个格子。 你从 $(2,1)$ 出发，必须以 $(2,m)$ 作为路径的终点。从格子 $(i,j)$ 出发，你可以前往： - $(i-1,j+1)$ —— 仅当 $i>1$ 时可以， - $(i,j+1)$， - $(i+1,j+1)$ —— 仅当 $i

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 10^4$，$3 \leq m \leq 10^{18}$），分别表示障碍物的数量和矩阵的列数。 接下来 $n$ 行，每行包含三个整数 $a_k$、$l_k$ 和 $r_k$（$1 \leq a_k \leq 3$，$2 \leq l_k \leq r_k \leq m-1$），表示一个障碍物阻挡了所有 $(a_k,j)$，其中 $l_k \leq j \leq r_k$。有些格子可能被多个障碍物阻挡。

输出从 $(2,1)$ 到 $(2,m)$ 的不同路径数，对 $10^9+7$ 取模。如果无法从 $(2,1)$ 到达 $(2,m)$，则输出 $0$。

由 ChatGPT 4.1 翻译