C. Youth Divisions
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A football club is reorganizing its youth divisions to take part in a championship organized by the FFT, the Tengo-lengo-tengo Football Federation.

There are $$$N$$$ available professionals, and each professional has a main role in a coaching staff.

Roles are represented by integers. For example, role $$$1$$$ may represent a head coach, role $$$2$$$ a fitness coach, role $$$3$$$ a physiotherapist, role $$$4$$$ a performance analyst, and role $$$5$$$ a goalkeeper coach.

The $$$i$$$-th professional has role $$$A_i$$$.

The club wants to divide all $$$N$$$ professionals into exactly $$$K$$$ coaching staffs, one for each youth division.

However, to avoid repeated responsibilities within the same staff, a coaching staff cannot contain two professionals with the same role. Also, every coaching staff must contain at least one professional.

Two divisions are considered different if there exists some group of professionals that forms a coaching staff in one division but does not form a coaching staff in the other. The order of the coaching staffs does not matter, and the order of professionals inside the same staff does not matter either.

Determine the number of different ways to form the $$$K$$$ coaching staffs, modulo $$$998244353$$$.

Input

The first line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \leq N, K \leq 10^5$$$).

The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$ ($$$1 \leq A_i \leq N$$$), where $$$A_i$$$ represents the main role of the $$$i$$$-th professional.

Output

The output must contain a single integer, the number of different ways to divide the professionals into exactly $$$K$$$ coaching staffs, modulo $$$998244353$$$.

Examples
Input
5 2
1 2 2 1 3
Output
4
Input
3 3
1 2 3
Output
1
Note

Explanation for example 1

There are $$$5$$$ professionals and $$$2$$$ coaching staffs must be formed. The roles are:

  • Role $$$1$$$: $$$2$$$ professionals;
  • Role $$$2$$$: $$$2$$$ professionals;
  • Role $$$3$$$: $$$1$$$ professional.

One valid division is to put one professional with role $$$1$$$ and one professional with role $$$2$$$ in one coaching staff, and the remaining professionals in the other coaching staff.

No coaching staff contains two professionals with the same role, and every professional is used exactly once.

Explanation for example 2

There are $$$3$$$ professionals, all with different roles, and $$$3$$$ coaching staffs must be formed. The only valid division is to put one professional in each staff.