Let's define the niceness of a sequence of positive integers X1,X2,…,XN$X_1, X_2, \dots, X_N$ as the sum of greatest common divisors of all pairs of its elements, i.e.
N∑i=1N∑j=i+1gcd(Xi,Xj).∑i=1N∑j=i+1Ngcd(Xi,Xj).\sum_{i=1}^N \sum_{j=i+1}^N \mathrm{gcd}(X_i, X_j)\;.
For example, the niceness of the sequence [1,2,2]$[1, 2, 2]$ is gcd(1,2)+gcd(1,2)+gcd(2,2)=4$gcd(1, 2) + gcd(1, 2) + gcd(2, 2) = 4$.
You are given a sequence A1,A2,…,AN$A_1, A_2, \dots, A_N$; each of its elements is either a positive integer or missing.
Consider all possible ways to replace each missing element of A$A$ by a positive integer (not necessarily the same for each element) such that the sum of all elements is equal to S$S$. Your task is to find the total niceness of all resulting sequences, i.e. compute the niceness of each possible resulting sequence and sum up all these values. Since the answer may be very large, compute it modulo 109+7$10^9 + 7$.

-----Input-----
- The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
- The first line of each test case contains two space-separated integers N$N$ and S$S$. 
- The second line contains N$N$ space-separated integers A1,A2,…,AN$A_1, A_2, \dots, A_N$. Missing elements in this sequence are denoted by −1$-1$.

-----Output-----
For each test case, print a single line containing one integer — the total niceness modulo 109+7$10^9 + 7$.

-----Constraints-----
- 1≤T≤20$1 \le T \le 20$
- 1≤N,S≤50$1 \le N, S \le 50$
- 1≤Ai≤50$1 \le A_i \le 50$ or Ai=−1$A_i = -1$ for each valid i$i$

-----Subtasks-----
Subtask #1 (30 points):
- 1≤N,S≤18$1 \le N, S \le 18$
- 1≤Ai≤18$1 \le A_i \le 18$ or Ai=−1$A_i = -1$ for each valid i$i$
Subtask #2 (70 points): original constraints

-----Example Input-----
3
3 3
1 1 -1
4 8
1 -1 -1 3
3 10
-1 -1 -1

-----Example Output-----
3
23
150

-----Explanation-----
Example case 1: There is only one possible way to fill in the missing element; the resulting sequence is [1,1,1]$[1, 1, 1]$. Its niceness is 3$3$.
Example case 2: There is only three possible ways to fill in the missing elements; the resulting sequences are [1,1,3,3]$[1, 1, 3, 3]$, [1,3,1,3]$[1, 3, 1, 3]$, and [1,2,2,3]$[1, 2, 2, 3]$. The sum of their niceness is 8+8+7=23$8 + 8 + 7 = 23$.

```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 = 'mod = 10**9 + 7\r\ndef gcd(a,b): return b and gcd(b, a % b) or a\r\n\r\ndef fac50():\r\n    f = [0]*51\r\n    f[0] = 1\r\n    f[1] = 1\r\n    for i in range(1,51):\r\n        f[i] = (f[i-1]*i)%mod\r\n    return f\r\n\r\ndef gcd110():\r\n\r\n    gc = [[0]*111 for i in range(111)]\r\n    for i in range(111):\r\n        for j in range(111):\r\n            gc[i][j] = gcd(i,j)\r\n    return gc\r\n\r\nfactorials = fac50()\r\ngcds = gcd110()\r\n\r\ndef rule_asc(n,l):\r\n    a = [0 for i in range(n + 1)]\r\n    k = 1\r\n    a[1] = n\r\n    while k != 0:\r\n        x = a[k - 1] + 1\r\n        y = a[k] - 1\r\n        k -= 1\r\n        while x <= y and k < l - 1:\r\n            a[k] = x\r\n            y -= x\r\n            k += 1\r\n        a[k] = x + y\r\n        yield a[:k + 1]\r\n\r\ndef niceness(s):\r\n    t = 0\r\n    for i in range(len(s)):\r\n        for j in range(i+1,len(s)):\r\n            t = (t + gcds[s[i]][s[j]])%mod\r\n    return t\r\n\r\n\r\ndef permcount(s,c):\r\n    f = [s.count(x) for x in set(s)]\r\n    p = factorials[c]\r\n    for e in f:\r\n        p = (p*pow(factorials[e],mod-2,mod))%mod\r\n    return p\r\n\r\ndef main():\r\n\r\n    t  = int(input())\r\n\r\n    for i in range(t):\r\n\r\n        n,s = [int(item) for item in input().split()]\r\n        a = [int(item) for item in input().split()]\r\n        b = [i for i in a if i != -1]\r\n        s -= sum(b)\r\n        ones = a.count(-1)\r\n\r\n        if s < 0:\r\n            print(0)\r\n        elif (s == 0 and ones == 0):\r\n            print(niceness(a)%mod)\r\n        elif (s > 0 and ones == 0):\r\n            print(0)\r\n        else:\r\n\r\n            t = 0\r\n            for seq in rule_asc(s,ones):\r\n                if len(seq) == ones:\r\n                    p = permcount(seq,ones)\r\n                    t = (t + ((p%mod)*(niceness(b+seq)%mod))%mod)%mod\r\n\r\n            print(t)\r\n\r\ndef __starting_point():\r\n    main()\r\n\n__starting_point()'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 123571