Mock CCC '19 Contest 1 J5 - Pusheen Designs a Sushi Boat

Points: 7 (partial)

Time limit: 0.6s

Memory limit: 1G

Problem type

Pusheen has been seeing a lot of sushi in her life lately and has taken to designing a sushi boat! She has $N$ ~N~ pieces of sashimi prepared and wants to select exactly $K$ ~K~ of them to put on her sushi boat. To maximize how pleasant her sushi boat looks, she refuses to put two pieces of sashimi on the boat if they come from the same fish.

How many different sushi boats can Pusheen construct? Two boats are different if Pusheen selects one piece of sashimi in one boat but does not select it in the other. Note that multiple pieces of sashimi can come from the same fish!

Constraints

$1 \le K \le N \le 10^3$ ~1 \le K \le N \le 10^3~

$1 \le f_i \le N$ ~1 \le f_i \le N~

In tests worth 2 marks, $K = 1$ ~K = 1~.

In tests worth an additional 3 marks, $K \le 2$ ~K \le 2~.

Input Specification

The first line contains two space-separated positive integers, $N$ ~N~ and $K$ ~K~.

The next line contains $N$ ~N~ space-separated integers. Integer $i$ ~i~ on the line corresponds to $f_i$ ~f_i~ and indicates that piece $i$ ~i~ of sashimi came from fish $f_i$ ~f_i~.

Output Specification

Output the number of distinct sushi boats that Pusheen can come up with, modulo $998\,244\,353$ ~998\,244\,353~.

Sample Input

4 3
1 2 2 3

Sample Output

Sample Explanation

Pusheen must select the 1st and 4th pieces of sashimi, but can choose either the 2nd or 3rd piece. This gives the two boats that Pusheen can construct.

Comments

0

MarksonChen commented on May 10, 2021, 5:12 a.m. ← edit 3 →

I'm stuck on #23 in the 3rd subtask... I get [218,197,204,191,190] and K = 5 as the values for this question, so isn't the answer 218 x 197 x 204 x 191 x 190 = 317936109360?

1

SuperClash commented on May 10, 2021, 1:29 p.m.

Output the number of distinct sushi boats that Pusheen can come up, modulo 998244353