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

View as PDF

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 pieces of sashimi prepared and wants to select exactly 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

In tests worth 2 marks, .

In tests worth an additional 3 marks, .

#### Input Specification

The first line contains two space-separated positive integers, and .

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

#### Output Specification

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

#### Sample Input

4 3
1 2 2 3

#### Sample Output

2

#### 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.