Contest Setting

Interview

Time limit1sMemory limit512 MB

Summary

Count the ways to choose k problems whose difficulties are all distinct, given n problems and their difficulty values, modulo 998,244,353.

Level: Medium4 of 10
Topics: Math, Combinatorics, Hash map, Sorting
Solved: No attempts yet

Problem

A group of contest writers have written n problems and want to use k of them in an upcoming contest. Each problem has a difficulty level. A contest is valid if all of its k problems have different difficulty levels.

Compute how many distinct valid contests the contest writers can produce. Two contests are distinct if and only if there exists some problem present in one contest but not present in the other.

Print the result modulo 998,244,353.

Input

The first line of input contains two space-separated integers n and k (1 ≤ k ≤ n ≤ 1000).

The next line contains n space-separated integers representing the difficulty levels. The difficulty levels are between 1 and 109 (inclusive).

Output

Print the number of distinct contests possible, modulo 998,244,353.

Examples3

Example 1
Input
```
5 2
1 2 3 4 5
```
Expected output
```
10
```
Example 2
Input
```
5 2
1 1 1 2 2
```
Expected output
```
6
```
Example 3
Input
```
12 5
3 1 4 1 5 9 2 6 5 3 5 8
```
Expected output
```
316
```