**Problem**

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 % (10^{9}+ 7).

###### Input

A single line which contains the input string.

###### Output

A single line which contains the number of anagram strings which are palindrome % (10^{9} + 7).

###### Constraints

- 1<= length of string <= 10^5
- Each character of the string is a lowercase alphabet.

###### Sample Input

aaabbbb

###### Sample Output

3

**Explanation**

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

###### Solution

Consider a string of length n. To find its palindromic permutations, we could consider a substring of length n/2 having half of number of each character present in the original string. For example:

if **s** = **“ababbb”**, then its half substring would be **sub** = **“abb”**. So all the permutations of the string **sub** would be palindromic with the other half which is same as **sub** ie **“abb”**. Now, to find the number of **permutations of sub (“abb”)**, we could use the following formula:

Number of permutation for a string of length n having all unique characters isn!. If some of them are repeating, then formula isn!/ (k1!*k2!*k3!...)where k[i] is the number of times a char k_i appears in the string.

To calculate **n!/ (k1!*k2!*k3!…)%mod(10 ^{9}+ 7)**, we could use the modular multiplicative inverse discussed in this post.

**Code Implementation**

```
//
// main.cpp
// Game of Thrones II
//
// Created by Himanshu on 18/02/22.
//
#include<iostream>
#include<string>
#define mod 1000000007
using namespace std;
typedef long long ll;
void precompute (int n, ll fact[], ll invFact[], ll inv[]) {
fact[0] = 1;
for (int i=1; i<= n; i++) {
fact[i] = (fact[i-1]*i)%mod;
}
inv[1] = 1;
for (int i=2; i<= n; i++) {
inv[i] = ((mod - (mod/i))*inv[mod%i])%mod;
}
invFact[0] = invFact[1] =1;
for (int i=2; i<= n; i++) {
invFact[i] = (invFact[i-1]*inv[i])%mod;
}
}
int main() {
ll ans;
string s;
int *alph = new int[26]();
cin>>s;
int n = (int) s.size();
ll *fact = new ll[n/2 + 1]();
ll *inv = new ll[n/2 + 1]();
ll *invFact = new ll[n/2 + 1]();
for (int i=0; i<n; i++) {
alph[s[i] - 'a']++;
}
precompute(n/2, fact, invFact, inv);
ans = fact[n/2];
for (int i=0; i<=25; i++) {
ans = (ans*invFact[(alph[i]/2)])%mod;
}
cout<<ans<<endl;
return 0;
}
```

**Time Complexity: O(n)**