TwoPerLine | Topcoder Archive

Problem Statement

You have an N by N grid. You also have T identical tokens.

You want to place the tokens into the grid. Each token must be placed into one of the grid cells. Each grid cell must contain at most one token.

There is one extra constraint: each row and each column of the grid must contain at most two tokens.

Count all valid placements of tokens and return their count modulo 10^9 + 7.

Definition

Class:: TwoPerLine
Method:: count
Parameters:: int, int
Returns:: int
Method signature:: int count(int N, int T)
(be sure your method is public)

Constraints

N will be between 1 and 200, inclusive.
T will be between 0 and 2*N, inclusive.

Examples

```
3
```
```
6
```
```
Returns: 6
```
We are placing 6 tokens into a 3x3 grid. One valid placement of six tokens is shown below (O is a token, . is an empty cell). OO. O.O .OO The other five can be obtained from this one by permuting its rows.
```
7
```
```
0
```
```
Returns: 1
```
There is exactly one way to place zero tokens onto a 7x7 grid. The result is an empty grid.
```
100
```
```
3
```
```
Returns: 584328838
```
Almost all of the (100*100 choose 3) ways of placing three tokens onto a 100x100 grid are valid. The only invalid placements are those where all three tokens ended in the same line. There is exactly 200 * (100 choose 3) of those. Thus, the exact number of valid placements is 166584330000. The return value shown above is this number modulo 10^9 + 7.
```
6
```
```
4
```
```
Returns: 51525
```

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.