题目描述

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

现在徐老师规划了一下自己的时间

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

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

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

当然，徐老师既然选择了复习，那么至少会花 $1$ 秒在这门课的复习上

同时，徐老师觉得自己的语文成绩不太好，所以他希望至少有 $K$ 天学习的是语文

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

这里徐老师认为两个方案只要任意一天的复习科目或者复习时长不同，就是不同的方案

因为方案数太大了，所以他需要你将方案数对 $10007$ 取模

输入格式

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

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

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

输出格式

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

数据范围

对于$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$

样例输入

2 1
2 3
1 2

样例输出

13