{"raw_statement":[{"iden":"statement","content":"On Planet E, people like shopping a lot!\n\nHowever they do not have electronic payments and can only pay by coins. There are $n$ different coins on Planet E, with different integral values $c_0, c_1, \\\\dots, c_{n -1}$ respectively. The cashiers on Planet E always have infinite number of each coins for changes, and hence very often there are multiple ways to give an $m$ dollar change.\n\nThe people on Planet E believe that the number of ways to give change affect their luck throughout the day, but it is too hard for them to count the number.\n\nCan you help the people on Planet E to count the number of ways to give change? Since the number may be huge, you only need to answer the number module $1000000007$ ($10^9 + 7$).\n\nThe first line contains a positive integer $T$ ($T <= 10$), the number of testcases.\n\nEach testcase starts with a line consisting of two integers $n, m$ ($1 <= n <= 100$, $1 <= m <= 10000$), the number of coins and the amount of change. Then the following line consists of $n$ integers $c_0, c_1, \\\\dots, c_{n -1}$ ($1 <= c_i <= 10000$), the coin values.\n\nFor each testcase, output a single line consisting of the number of ways to give exactly $m$ dollar change, module $10^9 + 7$.\n\nIn the second case, the five ways are *3 + 7*, *5 + 5*, *2 + 3 + 5*, *2 + 2 + 3 + 3* and *2 + 2 + 2 + 2 + 2*.\n\n"},{"iden":"input","content":"The first line contains a positive integer $T$ ($T <= 10$), the number of testcases.Each testcase starts with a line consisting of two integers $n, m$ ($1 <= n <= 100$, $1 <= m <= 10000$), the number of coins and the amount of change. Then the following line consists of $n$ integers $c_0, c_1, \\\\dots, c_{n -1}$ ($1 <= c_i <= 10000$), the coin values."},{"iden":"output","content":"For each testcase, output a single line consisting of the number of ways to give exactly $m$ dollar change, module $10^9 + 7$."},{"iden":"note","content":"In the second case, the five ways are *3 + 7*, *5 + 5*, *2 + 3 + 5*, *2 + 2 + 3 + 3* and *2 + 2 + 2 + 2 + 2*."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ denote the number of coin types.  \n- Let $ m_k \\in \\mathbb{Z} $ denote the target change amount.  \n- Let $ C_k = (c_{k,0}, c_{k,1}, \\dots, c_{k,n_k-1}) $ be a sequence of positive integers representing coin values.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 10 $  \n2. For each $ k \\in \\{1, \\dots, T\\} $:  \n   - $ 1 \\le n_k \\le 100 $  \n   - $ 1 \\le m_k \\le 10000 $  \n   - $ 1 \\le c_{k,i} \\le 10000 $ for all $ i \\in \\{0, \\dots, n_k - 1\\} $  \n\n**Objective**  \nFor each test case $ k $, compute the number of non-negative integer solutions $ (x_0, x_1, \\dots, x_{n_k-1}) $ to:  \n$$\n\\sum_{i=0}^{n_k-1} x_i \\cdot c_{k,i} = m_k\n$$  \nOutput the result modulo $ 10^9 + 7 $.","simple_statement":"You are given n coin types with values c0, c1, ..., cn-1. You need to count the number of ways to make exactly m dollars using any number of each coin. Answer modulo 10^9 + 7.","has_page_source":false}