# HackerRank Tara's Beautiful Permutations problem solution

In this HackerRank Tara's Beautiful Permutations problem solution You are given Q queries where each query consists of some array A. For each A, help Tara count the number of possible beautiful permutations of the n integers in A and print the count, modulo 10 to power 9 plus 7, on a new line.

## Problem solution in Python.

```factorial=[1,]
for i in range(1,2001):
factorial.append(factorial[-1]*i)

pascal=[[0 for y in range(1001)] for x in range(1001)]

for i in range(1001):
pascal[i][0]=1
for j in range(1,i+1):
pascal[i][j]=pascal[i-1][j-1]+pascal[i-1][j]

#print(factorial)

for _ in range(int(input())):
m=int(input())
n=len(set(input().split()))
k=m-n

ans=0
f=1
for j in range(0,k+1):

kCj=pascal[k][j]
ans+=f*kCj*factorial[m-j]//(2**(k-j))
f=f*-1
print(ans%1000000007)
```

{"mode":"full","isActive":false}

## Problem solution in Java.

```import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

/*
* Complete the beautifulPermutations function below.
*/
static int beautifulPermutations(int[] arr) {
/*
*/
HashSet<Integer> used = new HashSet<Integer>();
int n = arr.length;
for(int i = 0; i < n; i++)
int k = n-used.size();
long start = (long)1;
long[][] dp = new long[n+1][k+1];
for(int i = 1; i <= n; i++){
start = (i*start)%1000000007;
dp[i][0] = start;
}
for(int i = 1; i < k+1; i++){
for(int j = 2*i; j < n+1; j++){
long val = dp[j][i-1];
if(dp[j][i-1] % 2 == 1)
val = dp[j][i-1] + 1000000007;
dp[j][i] = (-dp[j-1][i-1] + val/2+1000000007)%1000000007;
}
}
return (int)dp[n][k];
}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

int t = Integer.parseInt(scanner.nextLine().trim());

for (int tItr = 0; tItr < t; tItr++) {
int arrCount = Integer.parseInt(scanner.nextLine().trim());

int[] arr = new int[arrCount];

String[] arrItems = scanner.nextLine().split(" ");

for (int arrItr = 0; arrItr < arrCount; arrItr++) {
int arrItem = Integer.parseInt(arrItems[arrItr].trim());
arr[arrItr] = arrItem;
}

int result = beautifulPermutations(arr);

bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
}

bufferedWriter.close();
}
}
```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<utility>
#include<set>
#include<stack>
#include<list>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<cmath>
#include<cctype>

#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ren(i,a,b) for(int i=a;i>=b;i--)
#define ff first
#define ss second
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vll vector<long long int>
#define vii vector<int>
#define gi(n) scanf("%d",&n)
#define gll(n) scanf("%lld",&n)
#define gstr(n) scanf("%s",n)
#define gl(n) cin >> n
#define oi(n) printf("%d",n)
#define oll(n) printf("%lld",n)
#define ostr(n) printf("%s",n)
#define ol(n) cout << n
#define os cout<<" "
#define on cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define all(n) n.begin(),n.end()
#define present(s,x) (s.find(x) != s.end())
#define cpresent(s,x) (find(all(s),x) != s.end())
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
using namespace std;

typedef unsigned long long int ull;
typedef long long int ll;
typedef vector<vector<ll> > mat;

ll m=1e9+7,f[200005],inv[200005];

ll p(ll a,ll b)
{
ll r=1;
while(b)
{
if(b&1)
r=(r*a)%m;
a=(a*a)%m;
b/=2;
}
return r;
}

ll ncr(ll n,ll r)
{
if(r>n||r<0)
return 0;
ll k=(inv[r]*inv[n-r])%m;
k=(f[n]*k)%m;
return k;
}

int main()
{ios_base::sync_with_stdio(false);
int t;
gl(t);

f[0]=1;
rep(i,1,200004)
f[i]=(f[i-1]*i)%m;
inv[200004]=p(f[200004],m-2);
ren(i,200003,0)
inv[i]=(inv[i+1]*(i+1))%m;

ll in=p(2,m-2);
while(t--)
{
int n;
cin>>n;
map<int,int> m1;
rep(i,1,n)
{
int x;
cin>>x;
m1[x]++;
}
int c=0;
tr(m1,it)
{
if(it->ss==2)
c++;
}
ll ans=0;
rep(i,0,c)
{
ll sgn=1;
if(i%2==1)sgn=-1;
ll x=(ncr(c,i)*f[n-i])%m;
x=(x*p(in,c-i))%m;
//ol(x);on;
ans=(ans+sgn*x)%m;
if(ans<0)ans+=m;
}
ol(ans);on;
}
return 0;
}
```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include<stdio.h>
#include<stdlib.h>
#define m 1000000007u
#define m2 500000004u
typedef long long unsigned llu;
typedef unsigned u;
int S(const void*x,const void*y){return*(int*)x-*(int*)y;}
u C[2222][2222],A[2222],F[2222];
u P(u b,u e)
{
u r=1;
for(;e;e>>=1)
{
if(e&1)r=r*(llu)b%m;
b=b*(llu)b%m;
}
return r;
}
int main()
{
u t,n,i,j,k,d,r;
for(i=-1;++i<2222;)for(C[i][j=0]=1;j++<i;)
if((C[i][j]=C[i-1][j-1]+C[i-1][j])>=m)C[i][j]-=m;
for(F[i=0]=1;++i<2222;)F[i]=i*(llu)F[i-1]%m;
for(scanf("%u",&t);t--;)
{
scanf("%u",&n);
for(i=-1;++i<n;)scanf("%u",A+i);
qsort(A,n,sizeof(u),S);
for(i=d=0;++i<n;)d+=A[i]==A[i-1];
k=P(m2,d);r=0;
for(i=-1;++i<=d;)
{
j=C[d][i]*(llu)F[n-i]%m*(llu)k%m;
if((k<<=1)>=m)k-=m;
if(i&1)
{
if((r-=j)>m)r+=m;
}
else
{
if((r+=j)>=m)r-=m;
}
}
printf("%u\n",r);
}
return 0;
}
```

{"mode":"full","isActive":false}