궁극의 마법 직사각형 (어려움)
시간 제한1초메모리 제한1024 MB
3행 c열 표에 음이 아닌 정수를 채워 서로 다른 행에 있고 한 직선 위에 놓인 세 칸의 합이 모두 s가 되는 경우의 수를 10^9 + 9로 나눈 나머지로 구합니다.
문제
밥이 오늘 바빠서, 앨리스가 1인용 게임을 찾았다.
이 게임에서 앨리스는 정수 와 행이 개, 열이 개인 빈 표를 받는다. 앨리스는 표의 칸에 음이 아닌 정수를 채워야 한다.
서로 다른 행에 있고 중심이 한 직선 위에 놓인 세 칸을 삼중항이라고 한다. 이 게임의 목표는 모든 삼중항의 합이 같아지도록 표를 채우는 것이다.
열의 수 와 각 삼중항의 목표 합 가 주어졌을 때, 조건에 맞게 표를 채우는 방법의 수를 구하라. 이 수가 클 수 있으므로 로 나눈 나머지를 출력한다.
위: 열이 인 표에서 삼중항 하나의 예.
입력
첫 줄에 테스트 케이스의 수 가 주어진다. 각 테스트 케이스 앞에는 빈 줄이 하나 있다.
각 테스트 케이스는 공백으로 구분된 정수 와 가 한 줄에 주어진다.
출력
각 테스트 케이스마다 해의 개수를 로 나눈 나머지를 별도의 줄에 출력한다.
제한
힌트
첫 번째 테스트 케이스에는 삼중항이 다섯 개 있다. 정사각형의 각 열과 두 대각선이다. 각 삼중항의 합이 1이어야 하므로, 각 삼중항에는 0이 두 개, 1이 하나 들어가야 한다. 해는 다음 다섯 가지이다.
111 000 000 101 010
000 111 000 000 000
000 000 111 010 101
두 번째 테스트 케이스에서 유효한 34개의 해 중 하나는 1로 가득 찬 직사각형이다.