- Prepare
- Algorithms
- Dynamic Programming
- Wet Shark and Two Subsequences

# Wet Shark and Two Subsequences

# Wet Shark and Two Subsequences

One day, Wet Shark was given an array . As always, he started playing with its subsequences.

When you came to know about this habit, you presented him a task of finding all pairs of subsequences, , which satisfies all of the following constraints. We will represent a pair of subsequence as and

- and must be of same length, i.e., .

Please help Wet Shark determine how many possible subsequences and can exist. Because the number of choices may be big, output your answer modulo .

*Note:*

- Two segments are different if there's exists at least one index such that element is present in exactly one of them.
- Both subsequences can overlap each other.
- Subsequences do not necessarily have to be distinct

**Input Format**

The first line consists of 3 space-separated integers ,â€‰,â€‰, where denotes the length of the original array, , and and are as defined above.

The next line contains space-separated integers, , representing the elements of .

**Constraints**

**Output Format**

Output total number of pairs of subsequences, , satisfying the above conditions. As the number can be large, output it's modulo

**Sample Input 0**

```
4 5 3
1 1 1 4
```

**Sample Output 0**

```
3
```

**Explanation 0**

For array there are three pairs of subsequences: