After learning a lot about space exploration, a little girl named Ana wants to change the subject.

Ana is a girl who loves palindromes (string that can be read the same backwards as forward). She has learned how to check for a given string whether it's a palindrome or not, but soon she grew tired of this problem, so she came up with a more interesting one and she needs your help to solve it:

You are given an array of strings which consist of only small letters of the alphabet. Your task is to find how many palindrome pairs are there in the array. A palindrome pair is a pair of strings such that the following condition holds: at least one permutation of the concatenation of the two strings is a palindrome. In other words, if you have two strings, let's say "aab" and "abcac", and you concatenate them into "aababcac", we have to check if there exists a permutation of this new string such that it is a palindrome (in this case there exists the permutation "aabccbaa"). 

Two pairs are considered different if the strings are located on different indices. The pair of strings with indices $(i,j)$ is considered the same as the pair $(j,i)$.


-----Input-----

The first line contains a positive integer $N$ ($1 \le N \le 100\,000$), representing the length of the input array.

Eacg of the next $N$ lines contains a string (consisting of lowercase English letters from 'a' to 'z') — an element of the input array. 

The total number of characters in the input array will be less than $1\,000\,000$.


-----Output-----

Output one number, representing how many palindrome pairs there are in the array.


-----Examples-----
Input
3
aa
bb
cd

Output
1

Input
6
aab
abcac
dffe
ed
aa
aade

Output
6



-----Note-----

The first example:  aa $+$ bb $\to$ abba. 

The second example:  aab $+$ abcac $=$ aababcac $\to$ aabccbaa aab $+$ aa $=$ aabaa abcac $+$ aa $=$ abcacaa $\to$ aacbcaa dffe $+$ ed $=$ dffeed $\to$ fdeedf dffe $+$ aade $=$ dffeaade $\to$ adfaafde ed $+$ aade $=$ edaade $\to$ aeddea

Difficulty: MEDIUM_HARD
Tags: String algorithms

Starter code:

Solutions:
import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
MOD1 = 100000007
MOD2 = 100000007
evenStrDict = {}
oddStrDict = {}
cnt = 0
N = int(input())
for _ in range(N):
	p = input()
	countList = [0] * 26
	for elem in p:
		if elem < 97:
			break
		countList[elem - 97] += 1
	hash1 = 0
	hash2 = 0
	for i in range(26):
		if countList[i] % 2 != 0:
			hash1 += 1 << i
			hash1 %= MOD1
			hash2 += 1 << i
			hash2 %= MOD2
	if len(p) % 2 != 0:
		curKey = (hash1, hash2)
		if curKey in oddStrDict:
			cnt += oddStrDict[curKey]
			oddStrDict[curKey] += 1
		else:
			oddStrDict[curKey] = 1
		for i in range(26):
			newHash1 = hash1
			newHash2 = hash2
			if countList[i] % 2 != 0:
				newHash1 -= 1 << i
				newHash1 %= MOD1
				newHash2 -= 1 << i
				newHash2 %= MOD2
			else:
				newHash1 += 1 << i
				newHash1 %= MOD1
				newHash2 += 1 << i
				newHash2 %= MOD2
			newKey = (newHash1, newHash2)
			if newKey in evenStrDict:
				cnt += evenStrDict[newKey]
	else:
		curKey = (hash1, hash2)
		if curKey in evenStrDict:
			cnt += evenStrDict[curKey]
			evenStrDict[curKey] += 1
		else:
			evenStrDict[curKey] = 1
		for i in range(26):
			newHash1 = hash1
			newHash2 = hash2
			if countList[i] % 2 != 0:
				newHash1 -= 1 << i
				newHash1 %= MOD1
				newHash2 -= 1 << i
				newHash2 %= MOD2
			else:
				newHash1 += 1 << i
				newHash1 %= MOD1
				newHash2 += 1 << i
				newHash2 %= MOD2
			newKey = (newHash1, newHash2)
			if newKey in oddStrDict:
				cnt += oddStrDict[newKey]
print(cnt)


def zamien(S):
	A = 26 * [0]
	for znak in S:
		A[ord(znak) - ord('a')] += 1
	return ''.join([str(i % 2) for i in A])

def mainn():
	A = {}
	wynik = 0
	for i in range(int(input())):
		s = zamien(input())
		wynik += A.get(s, 0)
		for i in range(26):
			wynik += A.get(s[:i] + str((int(s[i]) + 1) % 2) + s[i + 1:], 0)
		A[s] = A.get(s, 0) + 1
	return wynik
print(mainn())


aw = [2 ** i for i in range(26)]
n = int(input())
d = dict()
ans = 0
for ir in range(n):
	st = input()
	es = 0
	for j in st:
		es = es ^ aw[ord(j) - 97]
	if es in d:
		ans += d[es]
	for j in range(26):
		es = es ^ aw[j]
		if es in d:
			ans += d[es]
		es = es ^ aw[j]
	if es in d:
		d[es] += 1
	else:
		d.update({es: 1})
print(ans)


import sys
from collections import defaultdict
input = lambda : sys.stdin.readline().rstrip()
n = int(input())
d = defaultdict(int)
for _ in range(n):
	s = input()
	(e, mask) = (defaultdict(int), 0)
	for ch in s:
		e[ch] += 1
	for ch in e:
		v = 1 << ord(ch) - ord('a')
		if e[ch] & 1:
			mask |= v
	d[mask] += 1
ans = 0
aa = list(d.keys())
for mask in aa:
	ans += d[mask] * (d[mask] - 1) // 2
	for bit in range(26):
		v = 1 << bit
		if mask & v > 0:
			ans += d[mask ^ v] * d[mask]
print(ans)


import sys
N = int(input())
string_count = {}
for _ in range(N):
	s = str(input())
	char_count = {}
	for c in s:
		char_count[c] = char_count.get(c, 0) + 1
	s0 = []
	for a in 'abcdefghijklmnopqrstuvwxyz':
		if char_count.get(a, 0) % 2 == 1:
			s0.append(a)
	s1 = ''.join(s0)
	string_count[s1] = string_count.get(s1, 0) + 1
pairs = 0
for (s, v) in list(string_count.items()):
	pairs += v * (v - 1) // 2
	for i in range(len(s)):
		pairs += v * string_count.get(s[:i] + s[i + 1:], 0)
print(pairs)


import sys
input = sys.stdin.readline

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)

def main():
	comp = []
	c = 1
	for i in range(27):
		comp.append(c)
		c *= 2
	n = int(input())
	d = {}
	table = []
	for i in range(n):
		k = [0] * 27
		s = input()
		for j in s:
			if ord(j) - ord('a') >= 0:
				k[ord(j) - ord('a')] += 1
		key = 0
		for i in range(26):
			if k[i] % 2:
				key += comp[i]
		table.append([k, key])
		if key in d:
			d[key] += 1
		else:
			d[key] = 1
	ans = 0
	for i in d.values():
		ans += i * (i - 1) // 2
	for i in table:
		for j in range(len(i[0])):
			if i[0][j] % 2:
				if i[1] - comp[j] in d.keys():
					ans += d[i[1] - comp[j]]
	print(int(ans))
	return
main()


def main():
	n = int(input())
	ans = 0
	d = {}
	for i in range(n):
		s = input()
		cur = 0
		for c in s:
			cur ^= 1 << ord(c) - ord('a')
		ans += d.get(cur, 0)
		for j in range(26):
			ans += d.get(cur ^ 1 << j, 0)
		t = d.get(cur, 0) + 1
		d[cur] = t
	print(ans)
	return
main()


n = int(input())
odd_occ = []
alphabet = 'abcdefghijklmnopqrstuvwxyz'
for k in range(n):
	s = input()
	occ = {}
	for l in range(len(s)):
		ltr = s[l]
		if not occ.get(ltr):
			occ[ltr] = 0
		occ[ltr] += 1
	odd_ltrs = ''
	for l in range(26):
		ltr = alphabet[l]
		if not occ.get(ltr):
			continue
		if occ[ltr] % 2 == 1:
			odd_ltrs += ltr
	odd_occ.append(odd_ltrs + '0')
count = {}
for i in odd_occ:
	if not count.get(i):
		count[i] = 0
	count[i] += 1
res = 0
for i in count:
	k = 0
	for j in range(len(i) - 1):
		if not count.get(i[:j] + i[j + 1:]):
			continue
		k += count[i[:j] + i[j + 1:]]
	res += count[i] * k
	res += count[i] * (count[i] - 1) // 2
print(res)


import collections
N = int(input())

def hash(s):
	wc = collections.Counter(s)
	x = ''
	for i in range(26):
		w = chr(ord('a') + i)
		c = wc[w]
		if c % 2 == 0:
			x += '0'
		else:
			x += '1'
	return x

def neighbor(s):
	for i in range(len(s)):
		yield (s[:i] + ('1' if s[i] == '0' else '0') + s[i + 1:])

def isneighbor(a, b):
	return sum([0 if a[i] == b[i] else 1 for i in range(len(a))]) == 1
m = collections.defaultdict(list)
for i in range(N):
	s = input()
	m[hash(s)].append(i)
even = 0
odd = 0
for (k, v) in m.items():
	lv = len(v)
	even += lv * (lv - 1) // 2
	for b in neighbor(k):
		if b in m:
			odd += lv * len(m[b])
print(even + odd // 2)


n = input()
n = int(n)
st = list()
store = {}
for i in range(n):
	x = input()
	t = 0
	for c in x:
		t ^= 2 ** (ord(c) - ord('a'))
	if not t in store:
		store[t] = 1
	else:
		store[t] += 1
	st.append(t)
res = 0
for x in st:
	store[x] -= 1
	if x in store:
		res += store[x]
	for i in range(26):
		if x ^ 2 ** i in store:
			res += store[x ^ 2 ** i]
print(res)


n = int(input())
s = [0] * n
for i in range(n):
	s[i] = input()
dic = {}
ans = 0
for i in range(n):
	temp = 0
	for k in range(len(s[i])):
		temp ^= 1 << ord(s[i][k]) - ord('a')
	if temp in list(dic.keys()):
		ans = ans + dic[temp]
	for j in range(26):
		chk = temp
		chk ^= 1 << j
		if chk in list(dic.keys()):
			ans = ans + dic[chk]
	if temp in list(dic.keys()):
		dic[temp] += 1
	else:
		dic[temp] = 1
print(ans)


n = int(input())
string_count = {}
for _ in range(n):
	s = str(input())
	item_count = {}
	for (i, c) in enumerate(s):
		item_count[c] = item_count.get(c, 0) + 1
	s0 = []
	for x in 'abcdefghijklmnopqrstuvwxyz':
		if item_count.get(x, 0) % 2 == 1:
			s0.append(x)
	s1 = ''.join(s0)
	string_count[s1] = string_count.get(s1, 0) + 1
points = 0
for (a, x) in string_count.items():
	points += x * (x - 1) // 2
	for i in range(len(a)):
		points += x * string_count.get(a[:i] + a[i + 1:], 0)
print(points)


n = int(input())
a = {}
ans = 0
for i in range(n):
	d = 0
	st = input()
	for j in st:
		d ^= 1 << ord(j) - ord('a')
	ans += a.get(d, 0)
	for k in range(26):
		ans += a.get(d ^ 1 << k, 0)
	t = a.get(d, 0) + 1
	a[d] = t
print(ans)


from collections import Counter
n = int(input())
strings = []
for i in range(0, n):
	counter = {x: 0 for x in range(ord('a'), ord('z') + 1)}
	napis = input()
	for val in napis:
		counter[ord(val)] = (counter[ord(val)] + 1) % 2
	napis = ''
	for (key, val) in counter.items():
		if val != 0:
			napis += chr(key)
	strings.append(napis)
c = Counter(strings)
strings = sorted(c.most_common(), key=lambda i: i[0])
count = 0
for (key, val) in strings:
	if val > 1:
		count += val * (val - 1) / 2
for charInt in range(ord('a'), ord('z') + 1):
	char = chr(charInt)
	copy = {}
	for (key, val) in strings:
		if char in key:
			copy[key.replace(char, '')] = copy.get(key.replace(char, ''), 0) + val
	for (key, val) in strings:
		if copy.get(key, 0) != 0:
			count += val * copy[key]
print(int(count))


from collections import Counter
n = int(input())
mp = Counter({'': 0})
for i in range(n):
	string = input()
	occ = [0] * 26
	for c in string:
		occ[ord(c) - ord('a')] += 1
		if occ[ord(c) - ord('a')] == 2:
			occ[ord(c) - ord('a')] = 0
	clean = []
	for idx in range(26):
		while occ[idx] > 0:
			clean.append(chr(idx + ord('a')))
			occ[idx] -= 1
	mp[''.join(clean)] += 1
ans = 0

def combs(n):
	return n * (n - 1) // 2
for key in mp:
	if len(key) == 1:
		ans += combs(mp[key]) + mp[key] * mp['']
	elif len(key) == 0:
		ans += combs(mp[key])
	else:
		ans += combs(mp[key])
		for idx in range(len(key)):
			ans += mp[key] * mp[key[0:idx] + key[idx + 1:]]
print(ans)


N = int(input())
repo = {}
total_count = 0
for i in range(N):
	val = input()
	num = 0
	for c in val:
		index = ord(c) - ord('a')
		num ^= 1 << index
	if num in repo:
		total_count += repo[num]
	for j in range(26):
		num2 = num ^ 1 << j
		if num2 in repo:
			total_count += repo[num2]
	if num in repo:
		repo[num] += 1
	else:
		repo[num] = 1
print(total_count)


from collections import Counter
s = []
for i in range(int(input())):
	x = [0] * 26
	for j in input().strip():
		x[ord(j) - 97] ^= 1
	s.append(''.join([str(y) for y in x]))
z = Counter(s)
an = 0
for j in s:
	x = list(j)
	for q in range(len(x)):
		if x[q] == '1':
			x[q] = '0'
			an += z[''.join(x)]
			x[q] = '1'
for j in z:
	an += z[j] * (z[j] - 1) // 2
print(an)


import os
import sys
from io import BytesIO, IOBase
from collections import Counter

def main():
	n = int(input())
	string_cnt = {}
	for _ in range(n):
		s = input()
		item_cnt = Counter(s)
		s0 = []
		for x in 'abcdefghijklmnopqrstuvwxyz':
			if item_cnt.get(x, 0) % 2:
				s0.append(x)
		s1 = ''.join(s0)
		string_cnt[s1] = string_cnt.get(s1, 0) + 1
	ans = 0
	for (key, val) in string_cnt.items():
		ans += val * (val - 1) // 2
		for i in range(len(key)):
			ans += val * string_cnt.get(key[:i] + key[i + 1:], 0)
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def daj_maske(slowo):
	maska = 0
	for litera in slowo:
		kod = ord(litera) - ord('a')
		maska ^= 1 << kod
	return maska
n = int(input())
L = []
for _ in range(n):
	slowo = input()
	L.append(slowo)
wynik = 0
zlicz = {}
for slowo in L:
	maska = daj_maske(slowo)
	wynik += zlicz.get(maska, 0)
	for i in range(26):
		wynik += zlicz.get(maska ^ 1 << i, 0)
	zlicz[maska] = zlicz.get(maska, 0) + 1
print(wynik)


import sys
import math
import collections
import heapq
import decimal
input = sys.stdin.readline
n = int(input())
d = {}
ans = 0
for i in range(n):
	s = input()
	k = len(s) - 1
	c = 0
	for j in range(k):
		c ^= 1 << ord(s[j]) - 97
	ans += d.get(c, 0)
	for j in range(26):
		ans += d.get(c ^ 1 << j, 0)
	k = d.get(c, 0) + 1
	d[c] = k
print(ans)