题目描述

我们来研究一下这样的一个序列变换过程。

现在有一个长度为 $N$ 的序列 $\{A_i\}$，序列元素从 $1\sim N$ 编号。你可以在序列上执行**至多 $M$ **次操作，每次操作你需要指定三个参数 $l, r, v$。这里 $1\le l\le r\le N, 1\le v\le N$，接着，对于编号值 $i$ 在 $[l,r]$ 范围内的每个元素 $A_i$ 我们执行 $A_i\leftarrow \min(A_i, v)$。

我们有一个长度为 $N$ 的目标序列 $\{B_i\}$，如果你的某一次操作结束之后，得到的序列和 $B$ 完全一致，那么你需要立刻停止操作。我们把每次执行的操作写下来，得到一个操作序列，我们称此序列为一个合法的操作序列。

这里再明确一下合法操作序列的定义：合法操作序列指的是这样一个操作序列，使得按序列顺序做完所有操作之后可以将 $A$ 转化为 $B$，且不存在这个序列的任意严格前缀满足此条件。

现在问题来了：请问长度不超过 $M$ 的不同的合法操作序列有多少个，考虑到答案可能很大，你只需输出答案对 $10^9+7$ 取模的结果。

输入格式

输入包含三行。

第一行两个正整数 $N$，$M$，意义如题面所述。

接下来一行 $N$ 个整数，描述序列 $\{A_i\}$，保证 $1\le A_i \le N+1$。

第三行 $N$ 个整数，描述序列 $\{B_i\}$，保证 $1\le B_i\le \min(A_i, N)$，且存在至少一个 $i$ 使得 $A_i \ne B_i$。

输出格式

输出一行一个整数，表示答案。

2 5
3 2
2 2

10

总共有 10 种可能的操作序列，令 $(l, r, v)$ 表示一个操作，我们有代表性地列举 $5$ 种可能操作序列列举如下：

(1, 1, 2)
(1, 2, 2)
(2, 2, 2) (1, 1, 2)
(2, 2, 2) (1, 2, 2)
(2, 2, 2) (2, 2, 2) (2, 2, 2) (2, 2, 2) (1, 1, 2)

子任务

• 任务一：10 分，$N\le 5, M\le 15$。
• 任务二：10 分，$N\le 20, M \le 10^9$。
• 任务三：15 分，$N\le 50, M\le 100, A_i\le 2$。
• 任务四：30 分，$N\le 30, M\le 50$。
• 任务五：20 分，$N\le 50, M\le 100$。
• 任务六：15 分，$N\le 100, M\le 10^9$。

提示

假设有 $n$ 个有限集合 $A_i$ ，那么我们有下式成立：

$$\left|\bigcap_i A_i \right| = \sum_{S\subseteq [n]} (-1)^{|S|+1}\left|\bigcup_{j\in S} A_j\right| $$

这个式子也被称为容斥原理，它在组合计数问题里有广泛应用。例如，假设我们有针对组合对象的 $n$ 种组合性质，并且我们说一个组合对象 $x$ 满足性质 $i$，当且仅当 $x\in A_i$ 。那么上式实际上给出了一种统计满足所有 $n$ 个性质的组合对象个数的方法。