12:17 (UTC): The sample input 1 and 2 were swapped. The error is now fixed. We are very sorry for your inconvenience.
There are N children in AtCoder Kindergarten, conveniently numbered 1 through N. Mr. Evi will distribute C indistinguishable candies to the children.
If child i is given a candies, the child's happiness will become x_i^a, where x_i is the child's excitement level. The activity level of the kindergarten is the product of the happiness of all the N children.
For each possible way to distribute C candies to the children by giving zero or more candies to each child, calculate the activity level of the kindergarten. Then, calculate the sum over all possible way to distribute C candies. This sum can be seen as a function of the children's excitement levels x_1,..,x_N, thus we call it f(x_1,..,x_N).
You are given integers A_i,B_i (1≦i≦N). Find  modulo 10^9+7.

-----Constraints-----
 - 1≦N≦400
 - 1≦C≦400
 - 1≦A_i≦B_i≦400 (1≦i≦N)

-----Partial Score-----
 - 400 points will be awarded for passing the test set satisfying A_i=B_i (1≦i≦N).

-----Input-----
The input is given from Standard Input in the following format:
N C
A_1 A_2 ... A_N
B_1 B_2 ... B_N

-----Output-----
Print the value of  modulo 10^9+7.

-----Sample Input-----
2 3
1 1
1 1

-----Sample Output-----
4

This case is included in the test set for the partial score, since A_i=B_i.
We only have to consider the sum of the activity level of the kindergarten where the excitement level of both child 1 and child 2 are 1 (f(1,1)).
 - If child 1 is given 0 candy, and child 2 is given 3 candies, the activity level of the kindergarten is 1^0*1^3=1.
 - If child 1 is given 1 candy, and child 2 is given 2 candies, the activity level of the kindergarten is 1^1*1^2=1.
 - If child 1 is given 2 candies, and child 2 is given 1 candy, the activity level of the kindergarten is 1^2*1^1=1.
 - If child 1 is given 3 candies, and child 2 is given 0 candy, the activity level of the kindergarten is 1^3*1^0=1.
Thus, f(1,1)=1+1+1+1=4, and the sum over all f is also 4.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import os\nimport sys\n\nif os.getenv("LOCAL"):\n    sys.stdin = open("_in.txt", "r")\n\nsys.setrecursionlimit(2147483647)\nINF = float("inf")\nIINF = 10 ** 18\nMOD = 10 ** 9 + 7\n\n\ndef ModInt(mod):\n    class _ModInt:\n        def __init__(self, value):\n            self.value = value % mod\n\n        def __add__(self, other):\n            if isinstance(other, _ModInt):\n                return _ModInt(self.value + other.value)\n            else:\n                return _ModInt(self.value + other)\n\n        def __sub__(self, other):\n            if isinstance(other, _ModInt):\n                return _ModInt(self.value - other.value)\n            else:\n                return _ModInt(self.value - other)\n\n        def __radd__(self, other):\n            return self.__add__(other)\n\n        def __mul__(self, other):\n            if isinstance(other, _ModInt):\n                return _ModInt(self.value * other.value)\n            else:\n                return _ModInt(self.value * other)\n\n        def __truediv__(self, other):\n            # TODO: 実装\n            raise NotImplementedError()\n\n        def __repr__(self):\n            return str(self.value)\n\n    return _ModInt\n\n\nMI = ModInt(MOD)\n# 解説AC\nN, C = list(map(int, sys.stdin.readline().split()))\nA = list(map(int, sys.stdin.readline().split()))\nB = list(map(int, sys.stdin.readline().split()))\n\n\ndef solve():\n    # P[n][c]: n^c\n    P = [[1] * (C + 1) for _ in range(max(B) + 1)]\n    P[0] = [MI(0)] * (C + 1)\n    for i in range(1, len(P)):\n        for c in range(1, C + 1):\n            P[i][c] = P[i][c - 1] * i\n\n    # cs[n][c]: 0^c + 1^c + ... + n^c\n    cs = [[0] * (C + 1) for _ in range(max(B) + 1)]\n    for c in range(C + 1):\n        s = 0\n        for i in range(len(P)):\n            s += P[i][c]\n            cs[i][c] = s\n\n    # S[i][c]: X[i]^c (A[i]<=X[i]<=B[i]) の合計\n    S = [[0] * (C + 1) for _ in range(N)]\n    for i in range(N):\n        for c in range(C + 1):\n            S[i][c] = cs[B[i]][c] - cs[A[i] - 1][c]\n\n    # dp[c]: 各項の次数が c で、i 番目の子供まで見たときの f(X) の値\n    dp = S[0][:]\n    for i in range(1, N):\n        for c in reversed(list(range(C + 1))):\n            s = 0\n            for j in range(c + 1):\n                s += dp[c - j] * S[i][j]\n            dp[c] = s\n    return dp[-1]\n\n\n# print(f_partial([1, 1]))\n# print(f_partial([1, 2]))\n# print(f_partial([2, 1]))\n# print(f_partial([2, 2]))\nprint((solve()))\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 18647