Dinara 有一个整数 $x$ 和两个长度为 $n$ 的数组 $a_1, \dots, a_n$ 和 $b_1, \dots, b_n$。她构造了一个 $n \times n$ 的矩阵 $M$，其中：

$$M_{i,j} = \begin{cases} x + a_i b_j & \text{当 } i = j \\ a_i b_j & \text{其他情况} \end{cases}$$

求矩阵 $M$ 的行列式对 $(10^9 + 7)$ 取模的结果。

输入格式

输入包含多组测试数据，以文件结束符（EOF）结束。 每组测试数据的第一行包含两个整数 $n$ 和 $x$。第二行包含 $n$ 个整数 $a_1, \dots, a_n$。第三行包含 $n$ 个整数 $b_1, \dots, b_n$。

• $1 \le n \le 10^5$
• $0 \le x, a_i, b_i \le 10^9$
• 所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一个整数，表示结果。

样例

样例输入 1

2 1
0 0
0 0
2 1
1000000000 1000000000
1000000000 1000000000
3 2
2 3 3
2 3 3

样例输出 1

1
99
96