{"problem":{"name":"[NOI2022] 移除石子","description":{"content":"你正在玩一个名为“移除石子”的小游戏。 有 $n$ 堆石子排成一行，第 $i$ 堆有 $a_i$ 枚，你的任务是通过如下的操作将所有石子移除： - 操作一：选择一堆石子，将其中的至少 $2$ 枚石子移除； - 操作二：选择一个连续的编号区间 $[l, r]$（$1 \\le l \\le r \\le n$）并满足 $r - l \\ge 2$，将其中的每一堆石子都恰好移除 $1$ 枚。 你可以采用","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8497"},"statements":[{"statement_type":"Markdown","content":"你正在玩一个名为“移除石子”的小游戏。\n\n有 $n$ 堆石子排成一行，第 $i$ 堆有 $a_i$ 枚，你的任务是通过如下的操作将所有石子移除：\n\n- 操作一：选择一堆石子，将其中的至少 $2$ 枚石子移除；\n- 操作二：选择一个连续的编号区间 $[l, r]$（$1 \\le l \\le r \\le n$）并满足 $r - l \\ge 2$，将其中的每一堆石子都恰好移除 $1$ 枚。\n\n你可以采用任意顺序执行任意多次上述两种操作，直到无法再执行操作为止。若最后你能将所有石子全部移除则胜利。\n\n你或许已经开始计算起了诸如“有多少种本质不同的操作方式”的问题，但实际玩起来你却发现自己总是在输。因此，你打算玩个小花招：在游戏开始时，你在手里偷偷藏有 $k$ 枚石子，在执行所有操作之前你**可以且必须**将这些石子放入某一堆或某几堆石子中。你期望这会提高自己的胜率，但也清楚这可能会使自己输掉原本可能胜利的游戏。\n\n现在，你可以自由选择一个初始局面进行游戏，具体而言，每个 $a_i$ 可以选择 $[l_i, r_i]$ 范围内的任意整数。你希望计算出，在多少种初始局面下，自己存在至少一种获胜的方案。由于答案很大，你只需要输出其对 $({10}^9 + 7)$ 取模的结果。**两个初始局面不同，当且仅当存在至少一个 $\\boldsymbol{1 \\le i \\le n}$ 使得两者的 $\\boldsymbol{a_i}$ 不相等，注意这里的“初始局面”指的是你放入 $\\boldsymbol{k}$ 枚石子之前的局面。**\n\n## Input\n\n**本题有多组测试数据。** 第一行一个正整数 $T$ 表示测试数据组数，接下来依次给出每组测试数据。\n\n对于每组测试数据，第一行两个整数 $n, k$，分别表示石子堆数和加入的石子个数，接下来 $n$ 行，每行两个非负整数 $l_i, r_i$ 表示每堆石子初始石子数的范围。\n\n## Output\n\n对于每组数据输出一行一个整数，表示可能获胜的局面数对$({10}^9 + 7)$ 取模的结果。\n\n[samples]\n\n## Note\n\n**【样例解释 \\#1】**\n\n共有 $2^4 = 16$ 种可能的初始局面，可以证明除了 $(0 \\ 0 \\ 0 \\ 0)$ 和 $(1 \\ 0 \\ 0 \\ 1)$ 这两种初始局面无法获胜以外，其余初始局面均存在获胜方案。例如，初始局面为 $(1 \\ 0 \\ 1 \\ 0)$ 时，你可以将手中的 $1$ 枚石子放入第 $2$ 堆石子，使局面变为 $(1 \\ 1 \\ 1 \\ 0)$，再对区间 $[1, 3]$ 使用一次操作二即可。\n\n----\n\n**【样例 \\#2】**\n\n见附件中的 `stone/stone2.in` 与 `stone/stone2.ans`。\n\n----\n\n**【样例 \\#3】**\n\n见附件中的 `stone/stone3.in` 与 `stone/stone3.ans`。\n\n----\n\n**【样例 \\#4】**\n\n见附件中的 `stone/stone4.in` 与 `stone/stone4.ans`。\n\n----\n\n**【数据范围】**\n\n对于 $100 \\%$ 的数据，保证 $T \\le 10$，$3 \\le n \\le 1000$，$0 \\le l_i \\le r_i \\le {10}^9$，$0 \\le k \\le 100$。\n\n| 测试点编号 | $n \\le$ | $k \\le$ | 特殊条件 |\n|:-:|:-:|:-:|:-:|\n| $1 \\sim 3$ | $5$ | $2$ | $r_i \\le 5$ |\n| $4 \\sim 5$ | $1000$ | $0$ | $l_i = r_i$ |\n| $6 \\sim 8$ | $1000$ | $100$ | $l_i = r_i$ |\n| $9 \\sim 11$ | $1000$ | $0$ | 无 |\n| $12 \\sim 13$ | $1000$ | $2$ | 无 |\n| $14 \\sim 15$ | $1000$ | $100$ | $r_i \\le 10$ |\n| $16 \\sim 20$ | $1000$ | $100$ | 无 |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8497","tags":["2022","NOI","O2优化","DP 套 DP"],"sample_group":[["1\n4 1\n0 1\n0 1\n0 1\n0 1\n","14\n"]],"created_at":"2026-03-03 11:09:25"}}