A7075 | 跳格子

## 数据范围

- $2 \le N \le 2 \times 10^5$；
- $1 \le K \le \min(N,10)$；
- 对所有 $j$，有 $1 \le L_j \le R_j \le N$；
- 对所有 $i \ne j$，区间 $[L_i,R_i]$ 与 $[L_j,R_j]$ 互不相交；
- 输入中的所有数都是整数。
### 样例解释 1

此时集合 $S$ 为区间 $[1,1]$ 和 $[3,4]$ 的并集：
$$ S = \{1,3,4\}. $$

从第 $1$ 个格子出发，到达第 $5$ 个格子的方案共有 $4$ 种：

1. 依次到达格子 $1,2,3,4,5$（每次移动 $1$ 格）；
2. 依次到达格子 $1,2,5$（先移动 $1$ 格，再移动 $3$ 格）；
3. 依次到达格子 $1,4,5$（先移动 $3$ 格，再移动 $1$ 格）；
4. 依次到达格子 $1,5$（直接移动 $4$ 格）。

因此答案为 $4$。

### 样例解释 2

此时集合 $S = \{3,5\}$。
从第 $1$ 个格子出发：

- 第一次移动可以到格子 $4$（加 $3$）或者格子 $6$（加 $5$，非法）；
- 从格子 $4$ 再移动 $3$ 或 $5$ 都会超出范围。

所以无法到达第 $5$ 个格子，方案数为 $0$。
### 样例解释 3

此时集合 $S = \{1,2\}$。
可以验证所有到达格子 $5$ 的方案对应于将数字 $1$ 和 $2$ 相加得到和为 $4$ 的不同拆分方式，一共有 $5$ 种：

- $1+1+1+1$；
- $1+1+2$；
- $1+2+1$；
- $2+1+1$；
- $2+2$。

因此答案为 $5$。