피보나치 수의 거듭제곱 합

피보나치 수는 가장 잘 알려지고 많이 연구된 수열 가운데 하나이다. 이 수들에서 나타나는 규칙은 중세 건축이나 살아 있는 자연 등 뜻밖의 분야에서도 발견된다. 한 연구자가 새로운 규칙을 찾았다고 생각하는데, 가설을 검증하려면 도움이 필요하다.

피보나치 수는 다음 점화식으로 정의한다: $F_1=1$, $F_2=1$, $F_i=F_{i-1}+F_{i-2}$.

연구자를 도와 처음 $n$개 피보나치 수의 $k$제곱 합 $\sum_{i=1}^{n} F_i^k$를 $10^9+23$으로 나눈 나머지를 구하라.

첫 줄에 테스트의 개수 $t$ ($1 \le t \le 100$)가 주어진다. 이어지는 $t$개 줄에는 각각 테스트가 하나씩 주어지며, 정수 $n$, $k$ ($1 \le n \le 10^9$, $1 \le k \le 10^{18}$)가 주어진다. $n$은 피보나치 수의 개수, $k$는 거듭제곱 지수이다.

각 테스트마다 처음 $n$개 피보나치 수의 $k$제곱 합을 $10^9+23$으로 나눈 나머지를 한 줄에 출력한다.