All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef is playing a new computer game in which he is the chef of a restaurant and is required to prepare the dishes ordered by the customers with high quality and in time.
Chef will start in level 1 and whenever Chef passes a level in this game he will advance to the next level, but if Chef fails, he will return to level 1.
Chef has already played N rounds, but he can't remember what the levels were in all the rounds. He will give you an array A of length N such that Ai is equal to -1 if Chef can't remember what level the i-th round was, otherwise it will contain positive integer denoting the level of the round.
Now Chef is asking you to count the number of ways to fill the missing numbers (ie. the -1s) of the array with level numbers, so that it corresponds to a valid game. Since the answer can be large, output it modulo 109+7.
First line contains an integer T, the number of test-cases.
First line of each test-case contains an integer N.
Second line contains N space-separated integers, which are the elements of the array A.
Output the answer for each test-case in new line, the number of ways modulo 109+7.
- 1 ≤ T ≤ 10,000
- 1 ≤ N ≤ 100,000
- sum of N in all test-cases will not exceed 100,000
- 1 ≤ Ai ≤ N or Ai = -1
Input: 1 6 1 1 2 -1 -1 2 Output: 2
The only two valid fully filled arrays are (1,1,2,3,1,2) and (1,1,2,1,1,2). Hence the answer is 2.
|Tags||combinatorics, cook79, easy-medium, kingofnumbers|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.