{"raw_statement":[{"iden":"statement","content":"You have been out of Syria for a long time, and you recently decided to come back. You remember that you have M friends there and since you are a generous man/woman you want to buy a gift for each of them, so you went to a gift store that have N gifts, each of them has a price.\n\nYou have a lot of money so you don't have a problem with the sum of gifts' prices that you'll buy, but you have K close friends among your M friends you want their gifts to be expensive so the price of each of them is at least D.\n\nNow you are wondering, in how many different ways can you choose the gifts?\n\nThe input will start with a single integer T, the number of test cases. Each test case consists of two lines.\n\nthe first line will have four integers N, M, K, D (0  ≤  N, M  ≤  200, 0  ≤  K  ≤  50, 0  ≤  D  ≤  500).\n\nThe second line will have N positive integer number, the price of each gift.\n\nThe gift price is  ≤  500.\n\nPrint one line for each test case, the number of different ways to choose the gifts (there will be always one way at least to choose the gifts).\n\nAs the number of ways can be too large, print it modulo 1000000007.\n\n"},{"iden":"input","content":"The input will start with a single integer T, the number of test cases. Each test case consists of two lines.the first line will have four integers N, M, K, D (0  ≤  N, M  ≤  200, 0  ≤  K  ≤  50, 0  ≤  D  ≤  500).The second line will have N positive integer number, the price of each gift.The gift price is  ≤  500."},{"iden":"output","content":"Print one line for each test case, the number of different ways to choose the gifts (there will be always one way at least to choose the gifts).As the number of ways can be too large, print it modulo 1000000007."},{"iden":"examples","content":"Input25 3 2 100150 30 100 70 1010 5 3 50100 50 150 10 25 40 55 300 5 10Output3126"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T, H \\in \\mathbb{R}_{\\geq 0} $ be given real numbers.  \nLet $ \\mathcal{P} $ be the parabola with vertex at $ (0, H) $ and passing through $ (\\pm T, 0) $.  \nLet $ \\mathcal{R} $ be the region bounded by $ \\mathcal{P} $ and the line segment from $ (-T, 0) $ to $ (T, 0) $.  \n\n**Constraints**  \n$ 0 \\leq T, H \\leq 20000 $, with 6 decimal digits precision.  \n\n**Objective**  \nFind the maximum radius $ R \\in \\mathbb{R}_{>0} $ of a circle entirely contained within $ \\mathcal{R} $, centered on the y-axis.  \n\nThe parabola is defined by:  \n$$\ny = H \\left(1 - \\frac{x^2}{T^2}\\right)\n$$  \n\nThe optimal circle is tangent to the parabola and rests on the x-axis. Its center is at $ (0, R) $, and its equation is:  \n$$\nx^2 + (y - R)^2 = R^2\n$$  \n\nFind $ R $ such that the circle is internally tangent to the parabola.","simple_statement":"A room has a parabolic wall with vertex at (0, H) and crossing the x-axis at (±T, 0), and a flat floor from (-T, 0) to (T, 0). Find the largest possible radius of a circle that fits entirely inside this room.","has_page_source":false}