N행 M열의 체스판과 k개의 킹말이 주어질 때 k개의 킹말이 서로 공격하지 않도록 배치하는 경우의 수를 구하는 프로그램을 작성하시오.

어느 두 개의 킹말이 서로 공격하는 경우는 상하좌우 또는 대각선으로 인접한 경우이다.

가능한 경우의 수가 매우 클 수 있으므로 10억 7로 나눈 나머지를 구하시오. 아래 그림은 N = 7, M = 7, k = 16일 때 서로 공격하지 않도록 배치한 한 가지 예이다.

킹말의 배치 timer 10s memory 256MB

킹말의 배치 10s 256MB