Fast Matrix Exponentiation
문제 정보
문제
행렬의 자승은 동적 계획법의 선형 점화식을 빠르게 계산하는 등의 여러 용도에 유용하게 쓰인다. 크기 100 이하의 정방행렬 A 와 1 이상의 정수 p 가 주어질 때, Ap 을 계산하는 프로그램을 작성하여라.
단 행렬의 큰 자승을 계산할 경우 숫자가 매우 커질 수 있기 때문에, 행렬의 각 원소에 대해 10007 에 대한 나머지를 계산하기로 한다.
입력
입력의 첫 줄에는 테스트 케이스의 수 C (<= 20) 이 주어진다.
각 테스트 케이스의 첫 줄에는 행렬의 크기 N (1 <= N <= 100) 과 승수 p (<= 1,000,000) 가 주어진다. 그 후 N 줄에 각각 N개의 정수로, 행렬의 원소들이 맨 윗줄 왼쪽부터 순서대로 주어진다.
출력
각 테스트 케이스마다 N줄로 행렬의 원소를 10007 로 나눈 나머지를 맨 윗줄 왼쪽부터 순서대로 출력한다.
예제 입력
2 2 10000 1 0 0 1 3 10 1 2 3 4 5 6 7 8 9
예제 출력
1 0 0 1 9488 388 1295 6136 9010 1877 2784 7625 2459
노트