在著名数学家 Swan 去世前的最后一天，他给世界留下了一道难题：给定整数 $n$ 和 $a_i$（其中 $0 \le i \le 4$），计算有多少个 $n$ 位整数，其十进制表示中数字 $i$ 出现的次数不超过 $a_i$ 次（且不包含数字 $5, 6, 7, 8, 9$）。本题中不允许出现前导零。

输入格式

输入的第一行包含一个整数 $T$ ($1 < T \le 10$)，表示需要处理的测试用例数量。每个测试用例占一行，包含六个整数，分别表示 $n$ 和 $a_0$ 到 $a_4$，其中 $2 \le n \le 15000$ 且 $0 \le a_i \le 30000$。

输出格式

对于每个测试用例，请先输出测试用例的编号，然后输出问题的答案，结果对 $10^9 + 7$ 取模。

样例

输入 1

10
5 0 1 2 3 4
5 1 1 1 1 1
5 2 2 2 2 2
5 3 3 3 3 3
5 3 2 1 3 2
5 3 2 0 0 0
5 0 0 0 5 0
7000 41 2467 6334 2500 3169
7000 7724 3478 5358 2962 464
7000 5705 4145 7281 827 1961

输出 1

Case #1: 535
Case #2: 96
Case #3: 1776
Case #4: 2416
Case #5: 1460
Case #6: 4
Case #7: 1
Case #8: 459640029
Case #9: 791187801
Case #10: 526649529