该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小 Z 的暑假还剩下 $n$ 天，他知道自己的语文和数学两门课成绩不太好，他希望用这 $n$ 天时间尽可能的再提高一些。

现在小 Z 规划了一下自己的时间：

在第 $i$ 天，他会选择语文和数学其中一门课进行复习

• 如果复习语文，则最多花 $A[i]$ 秒
• 如果复习数学，则最多花 $B[i]$ 秒

当然，小 Z 既然选择了复习，那么在每一天都至少会花 $1$ 秒在这门课的复习上。同时，小 Z 觉得自己的语文成绩不太好，所以他希望至少有 $K$ 天学习的是语文。

现在他想知道，他一共有多少种不同的复习方案？

注意：

• 两个方案只要任意一天的复习科目或者复习时长不同，就是不同的方案
• 因为方案数太大了，所以只需要输出方案数对 $10007$ 取模的结果

输入格式

从 study.in 文件读入数据。

第一行包含两个整数 $n$ 和 $K$。

第二行有 $n$ 个整数 $A[i]$。

第三行有 $n$ 个整数 $B[i]$。

输出格式

输出到 study.out 文件。

输出一行一个整数。表示可能的方案数模 $10007$ 的结果。

样例

2 1
2 3
1 2

13

41 19
4316 7046 5634 6569 3699 7773 4987 6398 8454 524 6307 4426 2039 9154 5382 115 9595 9033 4879 5985 4677 3776 1755 4352 9356 4034 9730 7387 1112 9104 3632 5559 1216 8774 308 2801 3366 5576 9439 7048 7805
8862 9259 6340 8321 449 1987 6461 8150 5337 9649 4997 9953 2308 8879 8072 4687 1834 8373 9991 5892 962 3892 5957 2314 7068 7060 4028 1358 2117 4202 1748 1995 1822 7008 7771 8773 6255 7336 7535 544 1908

4701

大样例

点击链接 study.zip 获取大样例输入数据和输出数据。

说明/提示

样例 1 解释

至少有一天在学习语文，那么小 Z 的学习情况可以是 语文、语文，语文，数学，数学 语文 这三种情况。

因为每一天的学习时长不同也看做不同的方案，那么有：

• 语文、语文：此时第一天可以是 $[1,2]$ 小时，第二天可以是 $[1,3]$ 小时，总共方案数为 $2*3=6$。
• 语文、数学：此时第一天可以是 $[1,2]$ 小时，第二天可以是 $[1,2]$ 小时，总共方案数为 $2*2=4$。
• 数学、语文：此时第一天可以是 $[1,1]$ 小时，第二天可以是 $[1,3]$ 小时，总共方案数为 $1*3=3$。

综上，总共的方案数为 $6+4+3=13$ 种。

数据范围

对于$30\%$的数据 $n \leq 50$。

对于$60\%$的数据 $n \leq 5000, 1 \leq K \leq 20, 1 \leq A[i], B[i] \leq 10007$。

对于$100\%$的数据：$1 \leq n \leq 100000, 1 \leq K \leq 20, 1 \leq A[i], B[i] \leq 10^9$。