답의 범위가 상당히 클 수 있는데, 혹시 모듈러 값이 조건에 빠져 있나요?

아니면 항상 long long 범위 내의 답이 나오는 테스트 케이스만 존재하나요?

생각한 해는 110*110 행렬 빠른 거듭제곱인데, 만약 행렬의 원소가 long long 범위를 넘어가서

빅인티져를 구현해야 한다면 스트라센 행렬곱셈에 카라츠바 긴자리 곱셈을 넣어도 시간 제한을 통과하지 못할 듯해서..

긴자리 정수를 사용해도 무난히 통과할 수 있는 더 빠른 솔루션이 존재하는지,

아니면 조건상 모듈러 값이 누락되어 있는 것인지 궁금합니다.

확인 부탁드립니다