# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* anky_301

*wuhudsm, satyam_343*

**Testers:***iceknight1093*

**Editorialist:**# DIFFICULTY:

TBD

# PREREQUISITES:

None

# PROBLEM:

Given an array A of size N, count the number of its subsequences that are permutations.

# EXPLANATION:

Let’s count permutations of length 1, 2, 3, \ldots, N separately and add them up.

For a permutation of length K, we need to:

- Choose exactly one 1
- Choose exactly one 2
- Choose exactly one 3

\vdots - Choose exactly one K

There are no further restrictions, since the order of the chosen elements doesn’t matter.

In particular, if there are \text{freq}[i] occurrences of element i in the array, then the number of ways to do the above is simply \text{freq}[1] \times \text{freq}[2] \times \text{freq}[3] \times \ldots \times \text{freq}[K] = \prod_{i=1}^K \text{freq}[i].

Adding this up for all K, our final answer is thus

After computing the frequency array, this value is easy to compute in \mathcal{O}(N^2) time.

To optimize it, note that that we’re essentially taking prefix *products* of the \text{freq} array, and all of those can be computed in \mathcal{O}(N) time total once \text{freq} is known, thus solving the problem in \mathcal{O}(N).

# TIME COMPLEXITY

\mathcal{O}(N) per test case.

# CODE:

## Setter's code (Python)

```
for test_cases in range(int(input())):
n = int(input())
l = list(map(int , input().split()))
m = 1000000007
d = {}
for i in l:
if i in d:
d[i]+=1
else:
d[i] = 1
x = 1
c = 0
p = 1
while (x in d) and d[x]>0:
cur = ((p%m )*(d[x]%m))%m
c += cur
p = cur
c = c%m
x+=1
print(c)
```

## Tester's code (C++)

```
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll TMD=1000000007;
const ll INF=2147483647;
int T,n;
ll ans,cur;
int cnt[N];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) cnt[i]=0;
for(int i=1;i<=n;i++)
{
int t;
scanf("%d",&t);
if(t<=n) cnt[t]++;
}
ans=0;cur=1;
for(int i=1;i<=n;i++) cur=(cur*cnt[i])%TMD,ans=(ans+cur)%TMD;
printf("%lld\n",ans);
}
return 0;
}
```

## Editorialist's code (Python)

```
mod = 10**9 + 7
for _ in range(int(input())):
n = int(input())
freq = [0]*(n+1)
for x in map(int, input().split()):
if x <= n: freq[x] += 1
cur, ans = 1, 0
for i in range(1, n+1):
cur = (cur * freq[i]) % mod
ans += cur
print(ans % mod)
```