-----Problem Statement-----
Chef studies combinatorics. He tries to group objects by their rang (a positive integer associated with each object). He also gives the formula for calculating the number of different objects with rang N as following:

the number of different objects with rang N = F(N) = A0 + A1 * N + A2 * N2 + A3 * N3.

Now Chef wants to know how many different multisets of these objects exist such that sum of rangs of the objects in the multiset equals to S. You are given the coefficients in F(N) and the target sum S. Please, find the number of different multisets modulo 1,000,000,007.

You should consider a multiset as an unordered sequence of integers. Two multisets are different if and only if there at least exists one element which occurs X times in the first multiset but Y times in the second one, where (X ≠ Y).

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. 

The first line of each test case contains four integers A0, A1, A2, A3. The second line contains an integer S.

-----Output-----
For each test case, output a single line containing a single integer - the answer to the test case modulo 1,000,000,007.

-----Constraints-----
- 1 ≤ T ≤ 500
- 1 ≤ S ≤ 100
- 0 ≤ Ai ≤ 1000
- Sum of all S for all test cases is not greater than 500. It's guaranteed that at least one Ai is non-zero.

-----Example-----
Input:
4
1 0 0 0
1
1 0 0 0
3
0 1 0 0
2
2 3 1 4
10

Output:
1
3
3
213986343

-----Explanation-----
Example case 2. 

In the second example function looks as follows F(N) = 1. So for each rang there is a single object of the rang. To get multiset with sum of rangs equal to 3, you can pick: three objects of rang 1, or one object of rang 1 and one of rang 2, or only one object of rang 3. 
Example case 3. 

In the third example function looks as follows F(N) = N. So, you have one distinct object of rang 1, two distinct objects of rang 2, three distinct objects of rang 3 and so on. To get
multiset with sum of rangs equal to 2, you can pick: two objects of rang 1, one of objects of rang 2 (two ways).

```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 = "# cook your dish here\nimport sys\n\nmod_val = 1000000007\nrang = [0]*101\npow_cache = [0]*102\nmultisets = {}\n\n\ndef mod_pow(base, pow):\n result = 1\n while pow:\n  if pow&1:\n   result = (result*base) % mod_val\n  base = (base*base) % mod_val\n  pow = pow>>1\n return result\n\n\ndef precalculate():\n\n for i in range(1, 102):\n  pow_cache[i] = mod_pow(i, mod_val-2)\n\n\ndef cal_recurse(i, target_sum):\n if target_sum == 0:\n  return 1\n if i>=target_sum:\n  return 0\n if (i, target_sum) in multisets:\n  return multisets[(i, target_sum)]\n ans = cal_recurse(i+1, target_sum)\n max_pos = target_sum//(i+1)\n choose = rang[i+1]%mod_val\n for j in range(1, max_pos+1):\n  temp = choose*cal_recurse(i+1, target_sum-j*(i+1))\n  # temp%=mod_val\n  ans += temp\n  ans %= mod_val\n  choose *= rang[i+1]+j\n  # choose %= mod_val\n  choose *= pow_cache[j+1]\n  choose %= mod_val\n multisets[i, target_sum] = ans\n return ans\n\n\ndef calculate(target_sum, rang_index):\n populate(target_sum, rang_index)\n return cal_recurse(0, target_sum)\n\n\ndef populate(target_sum, rang_i):\n for i in range(1, target_sum+1):\n  rang[i] = rang_i[0] + (rang_i[1] + (rang_i[2] + rang_i[3]*i)*i)*i\n\n\n_test_cases = int(input())\nprecalculate()\nfor _a_case in range(_test_cases):\n rang = [0]*101\n multisets = {}\n _rang_index = [int(i) for i in input().split(' ')]\n _target_sum = int(input())\n print(calculate(_target_sum, _rang_index))\n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 19998