문제
N행 M열의 체스판과 k개의 킹말이 주어질 때 k개의 킹말이 서로 공격하지 않도록 배치하는 경우의 수를 구하는 프로그램을 작성하시오.
어느 두 개의 킹말이 서로 공격하는 경우는 상하좌우 또는 대각선으로 인접한 경우이다.
가능한 경우의 수가 매우 클 수 있으므로 10억 7로 나눈 나머지를 구하시오. 아래 그림은 N = 7, M = 7, k = 16일 때 서로 공격하지 않도록 배치한 한 가지 예이다.
입력
첫 행에 테스트 케이스의 수 T (1 ≤ T ≤ 8)가 입력된다.
이어 T개의 행에 각각의 데이터가 입력된다.
각 데이터는 행의 수 N, 열의 수 M, 킹말의 수 k가 공백으로 구분되어 입력된다.
(2 ≤ N, M ≤ 15 , 1 ≤ k ≤ N×M)
출력
각 테스트케이스에 대하여 가능한 경우의 수를 10억 7로 나눈 나머지를 행으로 구문하여 출력한다.
예제
4
8 8 1
7 7 16
7 7 7
3 7 15
64
1
2484382
0
출처
idiopen 2013
로그인해야 코드를 작성할 수 있어요.