407865: GYM102911 B1 Biodiverse Subsequence

B1. Biodiverse Subsequencetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

The problem statements of Biodiverse Subsequence and Biodiverse Subarray are nearly identical, save for whether the sampled corals must form a subsequence or subarray of the given sequence. Despite this, the two are very different problems.

Biodiversity is one of the most important properties in any ecosystem, whether it's in a forest, a mangrove, or even the ocean. The Philippines is rich with species of flora and fauna that are endemic to the country. Cindy, an avid scuba diver, has accompanied a group of biologists that ventured to the Verde Island Passage to sample some coral species for their research. Of course, it is important that the samples that they choose properly reflect the diversity of marine life found at the Coral Triangle.

They find a row of $$$N$$$ corals and identify $$$K$$$ distinct species among them. We model this as a sequence of $$$N$$$ positive integers $$$A_1, A_2, \dots, A_N$$$. Each of the integers from $$$1$$$ to $$$K$$$ appears at least once, and these are the only integers to appear in the sequence. A sequence of numbers is called biodiverse if each of the integers from $$$1$$$ to $$$K$$$ appears at least once each in the sequence.

The researchers must choose a biodiverse subsequence of corals to sample from. A subsequence is any sequence that can be derived from the given sequence by deleting zero or more elements without changing the relative ordering of the remaining elements. In order to make a decision on which corals to sample, the researchers ask Cindy to count the number of biodiverse subsequences of $$$A$$$.

Help Cindy out?

Input

The first line of input contains two space-separated integers $$$N$$$ and $$$K$$$, the number of corals and the number of distinct species, respectively.

The second line of input contains $$$N$$$ space-separated integers $$$A_1$$$, $$$A_2$$$, $$$\cdots$$$, $$$A_N$$$, where $$$A_i$$$ is the species of the $$$i$$$th coral in the row.

Output

Output a single line containing a single integer, the number of biodiverse subsequences of $$$A$$$.

Scoring

$$$1 \leq K \leq N \leq 60$$$

$$$1 \leq A_i \leq K$$$ for all $$$i$$$.

There exists an $$$i$$$ such that $$$A_i = k$$$ for all $$$k$$$ from $$$1$$$ to $$$K$$$.

Subtask 1 (40 points):

$$$N \leq 15$$$

Subtask 2 (20 points):

$$$N \leq 30$$$

Subtask 3 (20 points):

$$$K \leq 2$$$

Subtask 4 (20 points):

No further constraints.

ExamplesInput

4 2
1 2 1 2

Output

9

Input

14 9
3 1 4 1 5 9 2 6 5 3 5 8 9 7

Output

189

Note

The below diagram shows the nine biodiverse subsequences that the researchers can choose from in the first sample test case.

The below diagram shows three of the 189 biodiverse subsequences that the researchers can choose from in the second sample test case.