Kebab Dreams

Vahtang Bumerang works at the famous fast-food chain Kebab House and must prepare n kebabs. The i-th kebab is expected to have (q_{i}) ingredients. He spends one second to add one ingredient, so a kebab normally takes (q_{i}) seconds. However, while working he sometimes dreams about his boomerang. Every dream lasts exactly one second and during that second he forgets to add an ingredient. Nevertheless, customers are happy as long as the i-th kebab has at least (x_{i}) ingredients. In other words, if Vahtang has a dream during some seconds allocated for a particular kebab, the final number of ingredients in that kebab will be (q_{i} - d_{i}), where (d_{i}) is the number of seconds he dreamed while preparing it, and we require [ q_{i} - d_{i} \ge x_{i} \quad\Longleftrightarrow\quad d_{i} \le q_{i} - x_{i}. ]

There is an extra twist: Vahtang never dreams twice in any consecutive (t+1) seconds. That is, if he dreams at some second, he cannot dream in the next t seconds. Given n, t, the arrays (q=[q_{1},q_{2},\dots,q_{n}]) and (x=[x_{1},x_{2},\dots,x_{n}]), count the number of valid ways for Vahtang to have dream seconds during his work such that for each kebab the number of dreams does not exceed (q_{i} - x_{i}). As the answer can be very huge, output it modulo (10^{9}+7).

inputFormat

The first line contains two integers n and t. The second line contains n integers (q_{1},q_{2},\dots,q_{n}). The third line contains n integers (x_{1},x_{2},\dots,x_{n}) with (0 \le x_{i} \le q_{i}).

outputFormat

Output a single integer — the number of valid ways modulo (10^{9}+7).

sample

1 1
3
2

4