짧은 함수

지난주 알고리즘 수업의 강사가 주어진 의사코드 함수의 출력을 구하는 과제를 냈다. 과제는 문제 하나뿐이지만 강사는 얕보지 말라고 경고했다.

길이가 $N$인 양의 정수 배열 $A[]$(인덱스는 $0$부터 $N-1$까지)와 정수 $K$가 주어진다. 다음 함수의 출력을 구하시오.

SomeFunction(A[0..N-1], N, K):
    B[0..N-1] = A[0..N-1]
    for i = 0 to K-1:
        A[0..N-1] = B[0..N-1]
        for j = 0 to N-1:
            B[j] = A[j] × A[(j + 2i) mod N]
    return B[0..N-1]

함수가 반환하는 $B[0..N-1]$의 값을 구하시오. 입력 $A[]$, $N$, $K$는 조교에게 문의하여 받으시오. 직접 구현하면 몇 시간이 걸릴 수 있으므로 더 빠른 방법이 필요하다.

$B[0..N-1]$의 값은 매우 클 수 있다. 각 원소를 $998\,244\,353$으로 나눈 나머지를 출력하라.

첫 줄에 두 정수 $N$과 $K$가 주어진다 ($1 \le N \le 100\,000$; $1 \le K \le 10^9$). 다음 줄에는 배열 $A$의 원소인 $N$개의 정수 $A_i$가 주어진다 ($1 \le A_i < 998\,244\,353$).

$N$개의 정수를 한 줄에 공백으로 구분하여 출력하라. 배열 $B[]$의 각 원소를 $998\,244\,353$으로 나눈 나머지이다.