{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eA thief made his way to a shop.\u003cbr\u003e\u003cbr\u003eThere are \\(n\\) kinds of products in the shop and an infinite number of products of each kind. The value of one product of kind \\(i\\) is \\(a_i\\).\u003cbr\u003e\u003cbr\u003eThe thief wonders how many way to take some products such that the value of them is exactly \\(k\\) (it\u0027s possible for some kinds to take several products of that kind).\u003cbr\u003e\u003cbr\u003eFind the answer modulo \\(10^9 +7\\).\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input gives the number of test cases, \\(T(1\\le T\\le 100)\\). \\(T\\) test cases follow.\u003cbr\u003e\u003cbr\u003eFor each test case, the first line contains two integers \\(n, k(1\\le n\\le 100,1\\le k\\le 10^{18})\\), the number of kinds of products and the value of products the thief will take. \u003cbr\u003e\u003cbr\u003eThe second line contains \\(n\\) integers \\(a_i (1\\le a_i\\le 10)\\) — the values of products for kinds from \\(1\\) to \\(n\\).\u003cbr\u003e\u003cbr\u003eIt is guaranteed that there are no more than 10 testcases with \\(n\u0026gt;50\\).\u003cbr\u003e\u003cbr\u003eIt is guaranteed that there are no more than 40 testcases with \\(n\u0026gt;20\\).\u003cbr\u003e\u003cbr\u003eIt is guaranteed that there are no more than 80 testcases with \\(n\u0026gt;10\\)."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, print a line with an integer, representing the answer, modulo \\(10^9+7\\)."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\n4 10\r\n1 2 5 10\r\n4 100\r\n1 2 5 10\r\n5 20\r\n1 1 1 1 1\r\n10 1000000000000\r\n1 2 3 4 5 6 7 8 9 10\r\n20 1000000000000000000\r\n1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e11\r\n2156\r\n10626\r\n321553432\r\n822368450\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}