B. Random Shuffle?
time limit per test
2 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

We have an array $$$a$$$ of $$$n$$$ integers, and an initially empty sheet of paper.

We will do the following operations in-order $$$m$$$ times:

  • We shuffle the array $$$a$$$.
  • We choose a random positive integer $$${k \le n}$$$.
  • We choose a random index $$${1 \le i \le k}$$$.
  • We write $$$a_i$$$ at the end of the paper.

You are asked to calculate the probability that the integers written on the sheet are non-decreasing. Output the calculated value modulo $$$998244353$$$.

Input

The first and only line contains two positive integers $$$n$$$ and $$$m$$$ $$${(1 \le n, \space m \le 10^6)}$$$ — the length of the array and the number of times we repeat the operations.

The following line contains $$$n$$$ integers $$$a_1, \space a_2, \space \dots, \space a_n$$$ $$$(1 \le a_i \le n)$$$ — the elements of the array $$$a$$$.

Output

Output one integer, the probability that the integers written on the sheet are non-decreasing modulo $$$998244353$$$.

Example
Input
3 2
1 1 2
Output
110916040
Note

The possible final sequences on the paper are :

  • $$$(1,1)$$$ with probability $$$\frac{4}{9}$$$
  • $$$(1,2)$$$ with probability $$$\frac{2}{9}$$$
  • $$$(2,1)$$$ with probability $$$\frac{2}{9}$$$
  • $$$(2,2)$$$ with probability $$$\frac{1}{9}$$$
Thus the answer is $$$\frac{4}{9} + \frac{2}{9} + \frac{1}{9} = \frac{7}{9}$$$.