题目描述

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

现在 cyw 规划了一下自己的时间

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

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

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

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

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

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

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

因为方案数太大了，所以她需要你将方案数对 $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