Game Of Thrones (how many permutation of a string is a palindrome)

Game Of Thrones - II 

This follows from Game of Thrones - I.

Now that the king knows how to find out whether a given word has an anagram which is a palindrome or not, he encounters another challenge. He realizes that there can be more than one palindrome anagrams for a given word. Can you help him find out how many palindrome anagrams are possible for a given word ?

The king has many words. For each given word, he needs to find out the number of palindrome anagrams of the string. As the number of anagrams can be large, the king needs the number of anagrams % (109+ 7).

Input format :
A single line which contains the input string

Output format : 
A single line which contains the number of anagram strings which are palindrome % (109 + 7).

Constraints : 
1<=length of string <= 10^5 
Each character of the string is a lowercase alphabet. 
Each test case has at least 1 anagram which is a palindrome.

Sample Input 01 :

aaabbbb

Sample Output 01 :

3 

Explanation : 
Three palindrome permutations of the given string are abbabba , bbaaabb and bababab.

Sample Input 02 :

cdcdcdcdeeeef

Sample Output 02 :

90

=================================editorial================================

Problem: Given a string such that at least one of anagram of string is palindrome. Tell how many anagram of given string will be palindrome.

Approach: Given a string tell how many anagram of given string will be palindrome. So we can consider a sub-string which we can get by taking half of number of each character. length of this sub-string will L/2 where L is length of original string. we can get permutation of given string then we can concatenate the reverse of given half. so get anagram of given string which will be palindrome.So, we can use following formula to get number of permutation of given first half.

So , as answer can be very huge . But as in question we are asked for number of permutations which are palindrome % 10^9+7 and we know 10^9 + 7 is a prime number. So, we can get it using modular inverse techniques.

=========================code==============================

#include<bits/stdc++.h>

using namespace std;

#define mod 1000000007

typedef long long int lli;

lli fact[100010];

int has[100];

lli ifact[100010];

lli pow(lli a, lli b, lli MOD) 

{

lli x = 1, y = a;

    while(b > 0) {

        if(b%2 == 1)

{

            x=(x*y)%MOD;

            

        }

        

        y = (y*y)%MOD;

        

        b /= 2;

    }

    return x;

}

lli modInverse(lli a, lli m) 

{

    return pow(a,m-2,m);

}

int main()

{

fact[0]=1;

for(lli i=1;i<=100000;i++) fact[i]=(fact[i-1]*i)%mod;

for(int i=0;i<=100000;i++) ifact[i]=pow(fact[i],mod-2,mod);

string s;

cin>>s;

int len=s.length();

for(int i=0;i<len;i++)

{

has[s[i]-'a']++;

}

lli ans=0;

 ans=fact[len/2];

 for(int i=0;i<=26;i++)

  {

  ans=(ans*ifact[has[i]/2])%mod;

  }

  cout<<ans<<endl;

}