{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"OUM is a one unit machine which processes jobs. Since it can\u0027t handle heavyweight jobs; jobs needs to be partitioned into units. Initially, all the job information and unit partitions are given as input. Then the machine allocates necessary time slots. And in each time slot it asks the user for the name of the job to be processed. After getting the name; the machine determines the next unprocessed unit of that job and processes that unit in that slot. If there is no such unit, the machine crashes. A job is said to be complete if all the units of that job are complete.\n\nFor example, let **J\u003csub\u003e1\u003c/sub\u003e** and **J\u003csub\u003e2\u003c/sub\u003e** be two jobs each having **2** units. So, OUM will create **4** time slots. Now the user can give **J\u003csub\u003e1\u003c/sub\u003e J\u003csub\u003e2\u003c/sub\u003e J\u003csub\u003e2\u003c/sub\u003e J\u003csub\u003e1\u003c/sub\u003e** as input. That means it completes the **1\u003csup\u003est\u003c/sup\u003e** unit of **J\u003csub\u003e1\u003c/sub\u003e** in time slot **1** and then completes the **1\u003csup\u003est\u003c/sup\u003e** unit of **J\u003csub\u003e2\u003c/sub\u003e** in time slot **2.** After that it completes the **2\u003csup\u003end\u003c/sup\u003e** unit of **J\u003csub\u003e2\u003c/sub\u003e** and **2\u003csup\u003end\u003c/sup\u003e** unit of **J\u003csub\u003e1\u003c/sub\u003e** in time slots **3** and **4** respectively. But if the user gives **J\u003csub\u003e1\u003c/sub\u003e J\u003csub\u003e1\u003c/sub\u003e J\u003csub\u003e2\u003c/sub\u003e J\u003csub\u003e1 \u003c/sub\u003e**as input, the machine crashes in time slot **4** since it tries to process **3\u003csup\u003erd\u003c/sup\u003e** unit of **J\u003csub\u003e1\u003c/sub\u003e** which is not available.\n\nNow, Sam is the owner of a software firm named ACM and he has **n** jobs to complete using OUM. He wants to complete **Job\u003csub\u003ei\u003c/sub\u003e** before **Job\u003csub\u003ei+1\u003c/sub\u003e** where **1 \u0026#8804; i \u0026lt; n**. Now he wants to know the total number of ways he can complete these jobs without crashing the OUM. He assigned you for this task. Two ways are different if at **t\u003csup\u003eth\u003c/sup\u003e** slot one processed a unit of **Job\u003csub\u003ei\u003c/sub\u003e** and another processed a unit of **Job\u003csub\u003ej\u003c/sub\u003e** where **i \u0026#8800; j**. For the example above, there are three ways:\n\n1. **J\u003csub\u003e1\u003c/sub\u003e J\u003csub\u003e1\u003c/sub\u003e J\u003csub\u003e2\u003c/sub\u003e J\u003csub\u003e2\u003c/sub\u003e**\n2. **J\u003csub\u003e1\u003c/sub\u003e J\u003csub\u003e2\u003c/sub\u003e J\u003csub\u003e1\u003c/sub\u003e J\u003csub\u003e2\u003c/sub\u003e**\n3. **J\u003csub\u003e2\u003c/sub\u003e J\u003csub\u003e1\u003c/sub\u003e J\u003csub\u003e1\u003c/sub\u003e J\u003csub\u003e2\u003c/sub\u003e**"}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026#8804; 100)**, denoting the number of test cases.\n\nEach case starts with an integer **n (1 \u0026#8804; n \u0026#8804; 1000)**. The next line contains **n** space separated positive integers **k\u003csub\u003e1\u003c/sub\u003e, k\u003csub\u003e2\u003c/sub\u003e, k\u003csub\u003e3\u003c/sub\u003e ... k\u003csub\u003en\u003c/sub\u003e**. Where, **k\u003csub\u003ei\u003c/sub\u003e** denotes the number of units for the **i\u003csup\u003eth\u003c/sup\u003e** job. You can assume that total number of units for all the jobs in any case is not greater than **10\u003csup\u003e6\u003c/sup\u003e**."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the result modulo **1000000007 (10\u003csup\u003e9\u003c/sup\u003e + 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\u003e2\n2\n2 2\n3\n2 2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 3\nCase 2: 45\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}