Problem statement

Given the string $ S $. Find the number of all anagrams in $ S $ that are palindromic.

An anagram of the string $ X $ is an anagram of $ Y $, which means that $ X $ is equal to $ Y $, or that the rearranged characters of $ X $ are equal to $ Y $. For example, for the string abcd, abcd and cbda are anagrams, but abed, cab and abcdd are not anagrams.

When the string $ X $ is a palindrome, it means that the reverse reading of $ X $ is equal to $ X $ itself. For example, abc and ab are not palindromes, and a and abccba are palindromes.

Constraint

* $ 1 \ leq | S | \ leq 40 $ ($ | S | $ is the length of the string $ S $)
* $ S $ contains only lowercase letters.
* The answer is guaranteed to be less than $ 2 ^ {63} $.



input

Input follows the following format.


$ S $

output

Output the number on one line.

Examples

Input

ab


Output

0


Input

abba


Output

2
import java.util.Scanner;

//Palindromic Anagram
public class Main{

	void run(){
		Scanner sc = new Scanner(System.in);
		long[] f = new long[21];
		f[0] = 1;
		for(int i=1;i<21;i++)f[i]=f[i-1]*i;
		char[] s = sc.next().toCharArray();
		int N = s.length;
		int[] c = new int[26];
		for(char r:s)c[r-'a']++;
		int odd = 0;
		long res = 0;
		for(int i=0;i<26;i++)odd+=c[i]%2;
		if(N%2==0){
			if(odd==0){
				res = f[N/2];
				for(int i=0;i<26;i++)if(c[i]!=0)res/=f[c[i]/2];
			}
		}
		else {
			if(odd==1){
				for(int i=0;i<26;i++)if(c[i]%2==1)c[i]--;
				res = f[(N-1)/2];
				for(int i=0;i<26;i++)if(c[i]!=0)res/=f[c[i]/2];
			}
		}
		System.out.println(res);
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}