Problem K
Half-Grid Coverings
A half-grid is an
![\includegraphics[scale=0.5]{halfgrid.png}](/problems/halfgridcoverings/file/statement/en/img-0001.png)
A covering of a half-grid of size
![\includegraphics[scale=0.5]{halfgridcoverings.png}](/problems/halfgridcoverings/file/statement/en/img-0002.png)
How many distinct coverings are there for a half-grid of
size
Two coverings are considered distinct if there exist two squares that are covered by the same rectangle in one covering, and different rectangles in the other.
Since the answer may be large, output it modulo
Input
The first line of the input contains a single integer
Each test case consists of a single line with two integers
It is guaranteed that the sum of
Output
For each test case, output a single integer —the number
of coverings for a half-grid of size
Sample Input 1 | Sample Output 1 |
---|---|
10 1 1 3 1 3 3 3 4 5 8 5 12345 18 50 18 999 400 1023 400 1000000 |
1 0 4 5 38 42 222407600 477638700 462086201 169511428 |