Unique Subsequence :
Difficulty Level : Hard
Submissions : 64
Asked In :
Marks :100
: 2 | : 0
Antro and his girlfriend decided to move their relationship to the next level and bought an array from a nearby array shop. As you have already guessed both of them are programmers.
A subsequence is a sequence that can be derived from the given array by deleting zero or more elements (not all) without changing the order of the remaining elements.
A unique subsequence is a subsequence such that all its elements are pairwise distinct.
Now to impress his girlfriend Antonio has to tell the number of ways to choose the unique/Distinct subsequence from this array. Antonio is facing difficulties with this and needs to help him!
The first line contains a single Integer N ($$$1 \le N \le 1e5$$$)
The next line contains N space-separated integers denoting the elements of the array Antonio and his girlfriend bought ($$$1 \le A_i \le 1e6$$$)
Print the total number of ways to choose a unique subsequence from the given array. As the answer can be very large print it modulo 10^9+7.
3 1 2 1
6
4 1 1 1 1
4
