TheProblemSetter | Topcoder Archive

Problem Statement

This problem wasn't originally going to be part of this contest.
Unfortunately, the problem setter made a fatal mistake in the problem that was supposed to be used originally - when creating the input for that problem, he accidentally erased some numbers from it.
Therefore, we decided to replace that problem with this one.

The input of the original problem consisted of a int[][] T, the elements of which are preceded by their sizes.
All elements of input are between 0 and 500, inclusive. For the purpose of this problem, we'll view it as a single int[] input.

Specifically, a valid input without erased numbers must look as follows:

First, L0=input[0].
Then, L0 integers - input[1] through input[L0]. This corresponds to the int[] T[0].
Then, L1=input[L0+1].
Then, L1 integers - input[L0+2] through input[L0+L1+1]. This corresponds to the int[] T[1].
Then, L2=input[L0+L1+2], etc. till the end of the input.

There must not be any integers left over at the end of the input.

For example, if T={{1,2,3},{3,5}}, then input={3,1,2,3,2,3,5}, and if T={{0,0,0},{},{4,3,2,1}}, then input={3,0,0,0,0,4,4,3,2,1}.

Some elements of input are deleted. A deleted element is represented by number -1.
Reconstructing the input means replacing all -1s in input by non-negative integers in such a way, that the resulting int[] is a valid input.
(In particular, all the elements of input that correspond to elements of int[]s T[i] must be between 0 and 500, inclusive.)

Compute and return the number of ways to reconstruct the input, modulo 1,000,000,007.

Definition

Class:: TheProblemSetter
Method:: test
Parameters:: int[]
Returns:: int
Method signature:: int test(int[] input)
(be sure your method is public)

Constraints

Each number of input will be between -1 and 500 inclusive.
input will contain betwen 1 and 2000 numbers inclusive.
At most 200 numbers in input will be equal to -1.

Examples

```
{1,-1}
```
```
Returns: 501
```
There are 501 possible values for the first and only element of the first and only int[] in T, T[0].
```
{1,2,3}
```
```
Returns: 0
```
There's only one way of reconstructing the input, so there's no need to guess any number. However, that input isn't valid.
```
{-1,-1,-1}
```
```
Returns: 252004
```

{-1,2,3,-1,4,5,-1,6,7,-1}

Returns: 127260013

{168,436,265,225,53,496,366,383,-1,281,91,467,221,364,99,439,272,417,282,104,268,496,281,101,398,417,59,239,487,494,253,243,212,487,333,44,460,137,189,445,87,315,463,84,
-1,485,434,150,432,-1,39,257,269,251,50,257,454,103,432,75,1,268,26,131,154,98,443,179,276,343,118,489,170,129,224,15,288,101,310,377,338,377,310,102,297,414,338,435,
302,114,1,188,50,420,337,341,65,191,95,5,462,316,326,159,375,270,225,391,493,64,134,265,34,364,60,210,313,371,161,-1,170,155,437,267,364,135,383,34,-1,16,-1,494,85,24,
175,246,107,399,247,445,154,4,4,403,327,424,193,149,291,376,230,73,440,250,431,183,78,178,254,130,275,239,305,307,123,13,411,287,329,445,305,201,265,19,99,427,481,136,
150,182,115,157,24,410,151,446,-1,116,240,-1,219,485,102,452,-1,108,160,297,466,467,164,491,250,386,423,377,182,118,425,406,296,273,276,323,324,119,310,14,473,241,3,161,
238,206,260,163,158,458,96,464,155,112,293,91,467,-1,40,421,1,413,35,153,442,378,471,38,180,5,476,142,188,224,38,385,149,344,369,413,242,112,235,-1,172,209,359,158,271,
25,140,167,190,81,464,121,23,151,113,250,337,422,169,48,304,434,16,408,77,106,295,-1,499,423,-1,248,106,275,57,167,19,213,150,99,367,52,6,481,18,446,120,76,118,365,373,
464,389,433,123,47,230,235,175,461,262,244,190,100,20,286,454,210,399,497,111,478,231,395,128,220,431,310,125,302,339,178,421,43,349,482,455,198,6,427,299,235,319,320,
-1,98,71,358,262,305,432,384,468,-1,367,27,49,147,310,292,60,292,286,457,15,170,123,339,9,331,279,225,322,303,-1,497,58,92,-1,159,62,494,375,81,181,56,46,415,252,296,29,
429,77,175,141,-1,415,341,488,458,102,479,410,-1,47,303,166,413,219,98,207,499,196,135,417,290,215,335,123,371,175,-1,303,364,235,156,169,209,134,-1,45,-1,156,154,449,
27,350,300,385,108,316,306,116,440,56,316,384,113,249,407,240,148,20,295,374,32,293,109,15,403,56,134,-1,284,0,436,128,52,459,84,439,115,315,276,114,187,0,236,335,242,
170,90,214,157,447,-1,228,67,-1,486,14,498,10,64,455,483,77,178,258,116,60,65,175,166,197,445,273,90,346,228,165,376,472,76,55,249,-1,421,275,300,39,2,179,-1,195,359,493,
127,435,204,140,492,104,372,76,191,255,214,249,155,-1,36,303,400,56,225,57,121,466,329,368,53,2,155,11,141,266,-1,2,458,233,413,360,3,199,458,262,315,82,267,90,424,98,37,
13,204,342,69,395,20,77,416,488,54,28,0,297,84,438,112,365,411,39,172,85,320,-1,497,-1,255,-1,347,118,190,434,318,388,69,247,13,27,242,500,162,155,24,334,78,202,217,-1,
-1,193,217,435,426,272,161,361,484,315,440,4,478,47,497,-1,296,59,-1,110,134,-1,22,386,77,121,381,340,192,85,253,337,33,32,4,207,83,253,483,240,139,389,277,442,353,474,
129,194,306,96,7,72,178,151,147,151,91,372,333,-1,426,481,248,189,444,271,101,251,228,148,102,293,205,55,481,142,38,276,325,2,107,299,234,380,169,84,356,373,54,433,399,
280,126,113,216,392,410,324,331,371,219,471,74,424,444,402,262,452,368,120,263,185,78,197,427,500,398,399,222,484,442,452,481,12,219,388,312,58,171,444,212,87,183,-1,300,
294,33,152,230,26,451,53,169,436,225,364,256,400,28,-1,176,76,347,27,287,430,96,397,132,61,489,416,259,220,321,28,-1,-1,186,61,382,431,69,301,322,101,267,104,284,157,98,
93,93,303,184,177,20,96,225,114,25,126,349,363,389,309,303,1,171,109,29,126,425,338,175,9,139,192,52,251,375,367,314,90,-1,-1,199,367,477,-1,244,300,91,344,259,435,10,94,
77,66,-1,-1,9,266,251,437,94,52,295,179,248,477,-1,121,54,407,443,173,145,482,50,219,465,202,371,363,345,124,434,430,154,448,80,134,499,144,356,11,418,126,400,89,246,90,
275,234,71,264,258,316,408,355,39,259,66,245,48,292,361,356,358,277,324,263,182,441,392,157,229,472,419,1,117,112,152,134,291,317,191,366,100,197,393,146,30,121,108,45,
467,499,475,84,488,208,45,404,446,18,405,133,464,24,435,330,360,294,305,380,389,198,304,301,276,369,121,153,108,-1,410,97,0,311,485,305,118,107,451,57,7,243,71,134,337,
95,178,357,279,340,57,237,111,116,282,442,46,438,249,403,54,298,70,184,388,112,104,42,148,360,42,483,240,156,54,58,135,110,433,304,480,216,-1,454,402,213,-1,349,5,-1,341,
465,253,373,362,373,199,452,474,459,268,70,497,34,270,54,135,39,435,311,253,477,10,149,393,402,401,243,456,360,407,405,189,236,382,194,428,-1,457,434,253,150,163,345,
157,244,476,496,413,441,-1,247,170,273,372,26,-1,198,447,475,247,202,49,118,309,452,408,0,25,138,438,120,19,146,123,6,448,132,268,295,212,368,-1,176,77,166,5,386,34,490,
171,178,189,391,-1,457,333,78,107,103,93,170,452,338,180,411,227,178,254,97,422,431,285,352,386,167,350,219,201,-1,379,57,306,233,7,115,62,129,323,18,248,126,36,411,469,
167,464,140,254,199,341,232,244,237,93,464,114,398,330,177,497,338,316,0,1,239,1,57,0}

Returns: 989405867

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.