시준이는 선형대수학을 공부하며 너무나 헷갈리는 게 있었다! 이는 기호가 의 전치행렬을 뜻하는지, 를 번 곱한 행렬을 뜻하는지였다.
한참 고민하던 시준이는 좋은 방법을 떠올렸다. 두 행렬이 같다면 어느 쪽으로 읽어도 상관없다! 그래서 시준이는 두 해석이 같은 행렬만 다루기로 했다.
이 문제에서는 헷갈리지 않도록 행렬 의 전치행렬을 로 쓴다. 는 의 행 열 원소를 행 열로 옮긴 행렬이다. 는 를 번 곱한 행렬이다.
행렬 중에서 모든 행과 모든 열에 이 정확히 하나씩 있고 나머지 칸이 모두 인 행렬을 치환행렬이라고 한다. 행렬의 개수를 더 쉽게 셀 수 있도록 치환행렬만을 고려하기로 하자.
과 가 주어질 때, 치환행렬 중에서 를 만족하는 것의 개수를 구해 보자.
첫째 줄에 두 정수 가 공백으로 구분되어 주어진다.
조건을 만족하는 치환행렬의 개수를 으로 나눈 나머지를 출력한다. 이 수는 소수이다.
인 치환행렬 는
으로, 총 4개이다.
