수학IV

수학IV에서는 경우의 수를 세는 방법을 배우고 다양한 문제를 풀어본다. 여러분이라면 이 문제도 풀 수 있을 것이다!

$1$부터 $N$까지의 수가 하나씩 적힌 카드 $N$장이 일렬로 놓여 있다. 왼쪽부터 $i$번째 위치를 $i$번 위치라고 부른다. 처음에 $i$번 위치에는 $A_i$가 적힌 카드가 있다.

시준이는 다음 연산을 정확히 $K$번 한다.

• $1 \le i < j \le N$인 두 정수 $i, j$를 고르고, $i$번 위치의 카드와 $j$번 위치의 카드를 서로 바꾼다.

매 연산에서 $(i, j)$를 고르는 방법은 $\cfrac{N(N−1)}{2}$가지이므로, $K$번의 연산을 하는 방법은 모두 가지다. 어떤 번째 연산에서 고른 가 하나라도 다르면, 두 방법을 서로 다른 방법으로 본다.

$K$번의 연산을 모두 마친 뒤 $i$번 위치에 $i$가 적힌 카드가 있으면, 그 카드를 제자리 카드라고 한다. 또, 어떤 방법으로 $K$번의 연산을 마쳤을 때 제자리 카드의 개수를 그 방법의 점수라고 한다. 가능한 $\left(\dfrac{N(N-1)}{2}\right)^K$가지 방법의 점수를 모두 더한 값을 구하라.

첫 번째 줄에 양의 정수 $N, K$가 공백으로 구분되어 주어진다.

두 번째 줄에 $N$개의 양의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다.

문제의 정답을 $998 \, 244 \, 353$로 나눈 나머지를 출력한다. 이 수는 소수이다.

• $2 \le N \le 2 \times 10^5$
• $1 \le K \le 10^{18}$