Read problems statements in Mandarin Chinese  and Russian. 
The staff of one of the most famous ChefLand's restaurants have just received the news! A delegation from the neighbouring country is going to visit the restaurant. The staff want to make this visit exciting and pleasant. Lucy is also a member of the staff and among all the things that the staff want to do, her assignment is to arrange the flowers on the tables.
Generally, there are 26 kinds of flowers, a small latin letter corresponds to a single kind. Equal letters correspond to equal kinds. Different letters correspond to different kinds. According to the old ChefLand tradition, one can make a bouquet from some flowers only if it is a substring of some magic string T. ChefLands make bouquets in such a manner that the order of flowers in them is important. The restaurant has a tradition to decorate a single table with N, not necessary different, bouquets. Their order matters.
Some decorations look really similar. Generally, two arrangements (let's call them A and B) are similar if B is a cyclic shift of A, or B is a reversed cyclic shift of A. For example the sequence ("aba", "c", "b") is a cyclic shift of a sequence ("b", "aba", "c"), and the sequence ("c", "b", "a", "e", "d") is a reversed cyclic shift of a sequence ("a", "b", "c", "d", "e").
Now Lucy thinks that the most beautiful bouquets are "symmetric" ones. The bouquet is "symmetric" if the string that corresponds to the arrangement of flowers in it is a palindrome (it reads from left to right the same as from right to left). 
So, she thinks that the decoration of the table will be especially beautiful if all the bouquets in it are "symmetric". But then, Lucy had realized that the number of such decorations of the tables can be less than the number of guests. She doesn't want to decorate two tables in a similar manner, so she would like to know the number of distinct  decorations such that no two tables looks similar.

------ Input ------ 

The first line of input consists of a single string T.

The second line of input consists of a single integer N.

------ Output ------ 

Output the number of distinct decorations.

------ Constraints ------ 

1 ≤ |T| ≤ 100000;

1 ≤ N ≤ 600;

String T consists only of lowercase English letters.

------ Example ------ 

Input:
aba
4

Output:
21

Source: codechef | Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

String algorithms

Combinatorics

Mathematics


Solutions:
import math
from collections import defaultdict

def calculate_list_of_primes(n):
	primes = []
	isprime = []
	for i in range(0, n + 1):
		isprime.append(True)
	for i in range(2, math.floor(math.sqrt(n)) + 1):
		if isprime[i] == True:
			for j in range(i ** 2, n + 1, i):
				isprime[j] = False
	for i in range(2, n):
		if isprime[i] == True:
			primes.append(i)
	return primes
prime_list = calculate_list_of_primes(600)

def calculate_euler_totient(n):
	totient = n
	for i in prime_list:
		if n % i == 0:
			totient = totient * (i - 1) // i
	return totient

def necklace_count(n, k):
	count = 0
	for i in range(1, n + 1):
		if n % i == 0:
			count = count + calculate_euler_totient(i) * k ** (n // i)
	count = count // n
	return count

def bracelet_count(n, k):
	count = necklace_count(n, k)
	if n % 2 == 0:
		count = count + (k + 1) * k ** (n // 2) // 2
	else:
		count = count + k ** ((n + 1) // 2)
	return count // 2

def modified_manacher(str):
	odd = [0]
	radius = []
	for i in range(1, len(str) + 2):
		radius.append(0)
	n = 0
	i = 1
	text = '$'
	delta = 0
	for c in str:
		s = i - radius[i] + delta
		text += c
		while i + radius[i] <= n:
			radius[i] = min(radius[s + n - i - delta], n - i)
			if i + radius[i] == n and text[i - radius[i] - 1 + delta] == c:
				radius[i] = radius[i] + 1
				break
			i = i + 1
		n = n + 1
		odd.append(2 * radius[i] + 1 - delta)
	even = [0]
	radius = []
	for i in range(1, len(str) + 2):
		radius.append(0)
	n = 0
	i = 1
	text = '$'
	delta = 1
	for c in str:
		s = i - radius[i] + delta
		text += c
		while i + radius[i] <= n:
			radius[i] = min(radius[s + n - i - delta], n - i)
			if i + radius[i] == n and text[i - radius[i] - 1 + delta] == c:
				radius[i] = radius[i] + 1
				break
			i = i + 1
		n = n + 1
		even.append(2 * radius[i] + 1 - delta)
	even_odd = []
	for i in range(0, len(even)):
		even_odd.append(max(even[i], odd[i]))
	left = []
	right = []
	for i in range(1, len(even)):
		left.append(i - even_odd[i])
		right.append(i - 1)
	d = defaultdict(list)
	for i in range(0, len(left)):
		d[right[i] - left[i] + 1].append([left[i], right[i]])
	counts = set()
	answer = 0
	for (key, value) in d.items():
		if len(value) > 1:
			for i in value:
				counts.add(hash(str[i[0]:i[1] + 1]))
		else:
			answer += 1
	answer += len(counts)
	return answer
t = input()
n = int(input())
k = modified_manacher(t)
print(bracelet_count(n, k))


import string

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

def fastExp(a, n):
	ans = 1
	while n != 0:
		if n & 1:
			ans *= a
		a *= a
		n >>= 1
	return ans

def polya(n, m):
	sum = 0
	for i in range(n):
		sum += fastExp(m, gcd(i, n))
	adj = n * [-1]
	for i in range(n):
		for j in range(n):
			adj[j] = (n + i - j) % n
		cnt = 0
		mark = n * [False]
		for j in range(n):
			if not mark[j]:
				cnt += 1
				k = j
				while True:
					mark[k] = True
					k = adj[k]
					if k == j:
						break
		sum += fastExp(m, cnt)
	return sum // (n << 1)
sigma = string.ascii_lowercase

class Node:

	def __init__(self, sz):
		self.sz = sz
		self.adj = [None for _ in sigma]
		self.suf = None

	def __getitem__(self, label):
		return self.adj[ord(label) - ord('a')]

	def __setitem__(self, label, x):
		self.adj[ord(label) - ord('a')] = x

class PalindromeTree:

	def __init__(self):
		self.odd = Node(-1)
		self.even = Node(0)
		self.even.suf = self.odd.suf = self.odd
		self.count = 0

	def build(self, s):
		last = self.odd
		for (i, ch) in enumerate(s):
			cur = last
			while s[i - cur.sz - 1] != ch:
				cur = cur.suf
			if cur[ch] is None:
				self.count += 1
				new = cur[ch] = Node(cur.sz + 2)
				deep = cur.suf
				while s[i - deep.sz - 1] != ch:
					deep = deep.suf
				new.suf = self.even if cur is deep else deep[ch]
			else:
				new = cur[ch]
			last = new.suf if new.sz == i + 1 else new

	def __len__(self):
		return self.count
s = input()
n = int(input())
tree = PalindromeTree()
tree.build(s)
print(polya(n, len(tree)))