You are given an array A of n elements. Count the number of non-empty unique subsequences of length k of A.
_A subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements._
### Input
- The first line contains 2 integers n,k.
- The second line contains n integers Ai.
### Output
- Print the number of unique subsequences, modulo 123456789.
### Constraints
- 1≤k≤n≤2000.
- 1≤Ai≤2000.
### Example
Input:
32122
Output:
2
