Ultimate magic rectangles (Easy)
시간 제한1초메모리 제한1024 MB
3행 c열 격자를 음이 아닌 정수로 채우되 모든 열과 두 대각선으로 이루어진 각 삼중항의 합이 s로 같아지도록 하는 채우기 경우의 수를 1e9+7로 나눈 나머지로 구한다.
문제
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 in 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 in such a way that each triplet will have the same sum.
You are given the number of columns c and the desired sum of each triplet s. Compute the number of ways to fill the table in the desired way. Since this number may be large, compute it modulo 109 + 9.
Above: one of the many triplets on a board with c = 8 columns.
입력
The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.
Each test case consists of one line containing two space-separated integers c and s.
출력
For each test case, print one integer on a separate line – the number of solutions, modulo 109 + 9.
제한
- 1 ≤ c ≤ 50
- 0 ≤ s ≤ 50
힌트
In the first test case there are five triplets: each column and both main diagonals of the 3 × 3 square. The sum of each triplet must be 1, which means that 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 × 4 rectangle full of 1s.