Ultimate magic rectangles (Hard)

Time limit1sMemory limit1024 MB

Summary

Count the ways to fill a 3-row, c-column grid with nonnegative integers so every triplet on a line across all three rows sums to s, modulo 10^9 + 9.

Level: Hard8 of 10
Topics: Math, Combinatorics, Dynamic programming
Solved: No attempts yet

Problem

Bob is busy today, so Alice has found a single-player game.

In this game, Alice is given an integer $s$ and an empty table with $r = 3$ rows and $c$ columns. Alice has to fill some nonnegative integers into the cells of the table.

Three cells are called a triplet if they lie in different rows and their centers lie on a straight line. The goal of the game is to fill the table so that each triplet has the same sum.

You are given the number of columns $c$ and the desired sum of each triplet $s$ . Count the ways to fill the table in the desired way. The count may be large, so print it modulo $10^9 + 9$ .

Above: one of the many triplets on a board with $c = 8$ columns.

Input

The first line of the input contains an integer $t$ , the number of test cases. Each test case is preceded by a blank line.

Each test case consists of one line with two space-separated integers $c$ and $s$ .

Output

For each test case, print the number of solutions modulo $10^9 + 9$ on a separate line.

Constraints

$1 \le c \le 1000$

$0 \le s \le 10^9$

Hint

In the first test case there are five triplets: each column and both main diagonals of the $3 \times 3$ square. The sum of each triplet must be 1, so each triplet must contain two 0s and a 1. These are the five solutions:

111   000   000   101   010
000   111   000   000   000
000   000   111   010   101

In the second test case, one of the 34 valid solutions is a $3 \times 4$ rectangle full of 1s.

Examples1

Example 1
Input
```
2

3 1

4 3
```
Expected output
```
5
34
```