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!
In tests worth 2 marks, .
In tests worth an additional 3 marks, .
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 the number of distinct sushi boats that Pusheen can come up, modulo .
4 3 1 2 2 3
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.