https://algospot.com/judge/problem/read/DEATH


걍 마르코프 체인 문제.


입력을 transition matrix로 변환. 이 행렬을 A라고 하자.


B = A^X 라면 각 쿼리 j에 대한 답은 B[1][j]. 


결국 A^X를 빨리 구하는게 문제인데 이건 exponentiation by squaring으로 하면됨. 총 시간 복잡도는 O(N^3 log X)