You are given an array $A$ of $n$ elements. Count the number of non-empty unique subsequences 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 an integer $n$.
- The second line contains $n$ integers $A_i$.
### Output
- Print the number of unique subsequences, modulo $123456789$.
### Constraints
- $1 \le n, A_i \le 10^6$.
### Example
Input:
```
3
1 2 1
```
Output:
```
6
```
Note: There are $8$ subsequences of $A$:
- $(\emptyset)$.
- $(1)$.
- $(2)$.
- $(1)$.
- $(1, 2)$.
- $(2, 1)$.
- $(1, 1)$.
- $(1, 2, 1)$.
After removing empty and duplicate subsequences, only $6$ subsequences remain.
