{"raw_statement":[{"iden":"statement","content":"You are running through a rectangular field. This field can be represented as a matrix with 3 rows and _m_ columns. (_i_, _j_) denotes a cell belonging to _i_\\-th row and _j_\\-th column.\n\nYou start in (2, 1) and have to end your path in (2, _m_). From the cell (_i_, _j_) you may advance to:\n\n*   (_i_ - 1, _j_ + 1) — only if _i_ > 1,\n*   (_i_, _j_ + 1), or\n*   (_i_ + 1, _j_ + 1) — only if _i_ < 3.\n\nHowever, there are _n_ obstacles blocking your path. _k_\\-th obstacle is denoted by three integers _a__k_, _l__k_ and _r__k_, and it forbids entering any cell (_a__k_, _j_) such that _l__k_ ≤ _j_ ≤ _r__k_.\n\nYou have to calculate the number of different paths from (2, 1) to (2, _m_), and print it modulo 109 + 7."},{"iden":"input","content":"The first line contains two integers _n_ and _m_ (1 ≤ _n_ ≤ 104, 3 ≤ _m_ ≤ 1018) — the number of obstacles and the number of columns in the matrix, respectively.\n\nThen _n_ lines follow, each containing three integers _a__k_, _l__k_ and _r__k_ (1 ≤ _a__k_ ≤ 3, 2 ≤ _l__k_ ≤ _r__k_ ≤ _m_ - 1) denoting an obstacle blocking every cell (_a__k_, _j_) such that _l__k_ ≤ _j_ ≤ _r__k_. Some cells may be blocked by multiple obstacles."},{"iden":"output","content":"Print the number of different paths from (2, 1) to (2, _m_), taken modulo 109 + 7. If it is impossible to get from (2, 1) to (2, _m_), then the number of paths is 0."},{"iden":"example","content":"Input\n\n2 5\n1 3 4\n2 2 3\n\nOutput\n\n2"}],"translated_statement":[{"iden":"statement","content":"你正在一个矩形场地上奔跑。这个场地可以表示为一个包含 #cf_span[3] 行和 #cf_span[m] 列的矩阵。#cf_span[(i, j)] 表示属于第 #cf_span[i] 行和第 #cf_span[j] 列的单元格。\n\n你从 #cf_span[(2, 1)] 出发，必须到达 #cf_span[(2, m)]。从单元格 #cf_span[(i, j)]，你可以移动到：\n\n然而，有 #cf_span[n] 个障碍物阻挡你的路径。第 #cf_span[k] 个障碍物由三个整数 #cf_span[ak]、#cf_span[lk] 和 #cf_span[rk] 表示，它禁止进入任何满足 #cf_span[lk ≤ j ≤ rk] 的单元格 #cf_span[(ak, j)]。\n\n你需要计算从 #cf_span[(2, 1)] 到 #cf_span[(2, m)] 的不同路径数量，并对 #cf_span[109 + 7] 取模输出。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n ≤ 104], #cf_span[3 ≤ m ≤ 1018]) —— 障碍物数量和矩阵的列数。\n\n接下来 #cf_span[n] 行，每行包含三个整数 #cf_span[ak]、#cf_span[lk] 和 #cf_span[rk] (#cf_span[1 ≤ ak ≤ 3], #cf_span[2 ≤ lk ≤ rk ≤ m - 1])，表示一个障碍物，它会阻挡所有满足 #cf_span[lk ≤ j ≤ rk] 的单元格 #cf_span[(ak, j)]。某些单元格可能被多个障碍物阻挡。\n\n请输出从 #cf_span[(2, 1)] 到 #cf_span[(2, m)] 的不同路径数量，对 #cf_span[109 + 7] 取模。如果无法从 #cf_span[(2, 1)] 到达 #cf_span[(2, m)]，则路径数量为 #cf_span[0]。"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n ≤ 104], #cf_span[3 ≤ m ≤ 1018]) —— 障碍物数量和矩阵的列数。接下来 #cf_span[n] 行，每行包含三个整数 #cf_span[ak]、#cf_span[lk] 和 #cf_span[rk] (#cf_span[1 ≤ ak ≤ 3], #cf_span[2 ≤ lk ≤ rk ≤ m - 1])，表示一个障碍物，它会阻挡所有满足 #cf_span[lk ≤ j ≤ rk] 的单元格 #cf_span[(ak, j)]。某些单元格可能被多个障碍物阻挡。"},{"iden":"output","content":"请输出从 #cf_span[(2, 1)] 到 #cf_span[(2, m)] 的不同路径数量，对 #cf_span[109 + 7] 取模。如果无法从 #cf_span[(2, 1)] 到达 #cf_span[(2, m)]，则路径数量为 #cf_span[0]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z} $, with $ 1 \\leq n \\leq 10^4 $, $ 3 \\leq m \\leq 10^{18} $.  \nLet $ G = ([3] \\times [m], E) $ be a directed grid graph, where $ [k] = \\{1, 2, \\dots, k\\} $, and edges exist from $ (i, j) $ to $ (i', j+1) $ if $ |i - i'| \\leq 1 $, for all $ j \\in [m-1] $.  \n\nLet $ O = \\{(a_k, l_k, r_k) \\mid k \\in [n]\\} $ be a set of obstacles, where each obstacle blocks all cells $ (a_k, j) $ for $ j \\in [l_k, r_k] $.  \n\nLet $ S = (2, 1) $ be the start, and $ T = (2, m) $ be the target.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^4 $, $ 3 \\leq m \\leq 10^{18} $  \n2. For each obstacle $ (a_k, l_k, r_k) $: $ 1 \\leq a_k \\leq 3 $, $ 2 \\leq l_k \\leq r_k \\leq m-1 $  \n3. Cells blocked by obstacles are unreachable.  \n4. Paths consist of moves only from column $ j $ to $ j+1 $, and between rows differing by at most 1.  \n\n**Objective**  \nCompute the number of paths from $ (2,1) $ to $ (2,m) $, moving only rightward and between adjacent rows, avoiding all blocked cells, modulo $ 10^9 + 7 $.","simple_statement":null,"has_page_source":false}