#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define maxn 2222222
#define base1 1000003LL
#define base2 239LL
#define mod1 1000000007LL
#define mod2 1000000009LL
pair< long long ,long long > a[ maxn] ;
int an,i,j,N,K,l,r,lT,k,f[ maxn] ,P[ maxn] ,was[ maxn] ,cycles,Count[ maxn] ,q,c[ maxn] ,Q[ maxn] ,size,R[ maxn] ,s[ maxn] ;
long long pw1[ maxn] ,pw2[ maxn] ,sha1[ maxn] ,sha2[ maxn] ,pw,ret;
char T[ maxn] ;
pair< long long ,long long > gethash( int j,int x) { // hash of a [j; j+x) substring
return make_pair( ( ( sha1[ j] - sha1[ j+ x] + mod1) * pw1[ j] ) % mod1,( ( sha2[ j] - sha2[ j+ x] + mod2) * pw2[ j] ) % mod2) ;
}
void getOddSubpalindromes( ) { // Manacher algo for finding all odd sub palindromes. one can prove that there will be no more than N distinct such palindromes
for ( i= 0 ,l= 0 ,r= - 1 ; i< lT; i++ ) {
k= ( i> r? 0 : min( f[ l+ r- i] ,r- i) ) + 1 ;
while ( i+ k< lT&& i- k>= 0 && T[ i+ k] == T[ i- k] ) {
a[ ++ an] = gethash( i- k,2 * k+ 1 ) ;
++ k;
}
while ( i+ k>= lT|| i- k< 0 || T[ i+ k] ! = T[ i- k] ) -- k;
f[ i] = k;
a[ ++ an] = gethash( i- k,2 * k+ 1 ) ;
a[ ++ an] = gethash( i,1 ) ;
if ( i+ k> r) l= i- k,r= i+ k;
}
}
void getEvenSubpalindromes( ) { // Manacher algo for finding all even sub palindromes. one can prove that there will be no more than N distinct such palindromes
for ( i= 0 ; i< lT; i++ ) f[ i] = 0 ;
for ( i= 0 ,l= 0 ,r= - 1 ; i< lT; i++ ) {
k= ( i> r? 0 : min( f[ l+ r- i+ 1 ] ,r- i+ 1 ) ) + 1 ;
while ( i+ k- 1 < lT&& i- k>= 0 && T[ i- k] == T[ i+ k- 1 ] ) {
a[ ++ an] = gethash( i- k,2 * k) ;
++ k;
}
f[ i] = -- k;
if ( i+ k- 1 > r) l= i- k,r= i+ k- 1 ;
}
}
void buildHash( ) { // preprocess hashes
pw1[ 0 ] = pw2[ 0 ] = 1 ;
for ( i= 1 ; i<= lT; i++ ) pw1[ i] = ( pw1[ i- 1 ] * base1) % mod1,pw2[ i] = ( pw2[ i- 1 ] * base2) % mod2;
sha1[ lT- 1 ] = sha2[ lT- 1 ] = T[ lT- 1 ] ;
for ( i= lT- 2 ; i+ 1 ; i-- ) {
sha1[ i] = ( sha1[ i+ 1 ] + pw1[ lT- i- 1 ] * T[ i] ) % mod1,sha2[ i] = ( sha2[ i+ 1 ] + pw2[ lT- i- 1 ] * T[ i] ) % mod2;
}
}
long long carry= 0 ;
int bn,b[ maxn] ;
void outputTheAnswer( ) {
carry= 0 ;
for ( i= maxn- 1 ; i+ 1 ; i-- ) {
carry= carry* an+ Count[ i] ;
if ( carry>= size|| bn) {
b[ ++ bn] = carry/ size;
carry% = size;
}
}
assert ( carry== 0 ) ;
c[ c[ 0 ] = 1 ] = 0 ;
for ( i= 1 ; i<= bn; i++ ) {
for ( j= 1 ; j<= c[ 0 ] ; j++ ) c[ j] * = an;
c[ 0 ] + = 20 ,c[ 1 ] + = b[ i] ;
for ( j= 1 ; j<= c[ 0 ] ; j++ ) {
c[ j+ 1 ] + = c[ j] / 10 ;
c[ j] % = 10 ;
}
while ( c[ 0 ] > 1 && c[ c[ 0 ] ] == 0 ) -- c[ 0 ] ;
}
for ( i= c[ 0 ] ; i; i-- ) putchar ( '0' + c[ i] ) ;
puts ( "" ) ;
}
vector< int > vec;
set< vector< int > > S;
void go( int * A) { // count the number of cycles in the permutation
int i;
vec.clear ( ) ;
for ( i= 1 ; i<= N; i++ ) vec.push_back ( A[ i] ) ;
if ( S.find ( vec) ! = S.end ( ) ) return ; // uniqueeness checking (maybe, it's not necessary)
S.insert ( vec) ;
++ size; cycles= 0 ;
for ( i= 1 ; i<= N; i++ ) if ( was[ i] ! = size) {
++ cycles;
for ( q= i; was[ q] ! = size; q= A[ q] ) was[ q] = size;
}
++ Count[ cycles] ;
}
int main ( int argc, char * const argv[ ] ) {
gets ( T) ;
lT= strlen ( T) ;
buildHash( ) ;
getOddSubpalindromes( ) ;
getEvenSubpalindromes( ) ;
sort( a+ 1 ,a+ an+ 1 ) ;
an= unique( a+ 1 ,a+ an+ 1 ) - ( a+ 1 ) ;
if ( an== 1 ) { // if there's only one palindrome (<=> |T|=1)
cout << 1 << endl;
return 0 ;
}
scanf ( "%d" ,& N) ;
for ( i= 1 ; i<= N; i++ ) { // generating all reachable permutations
// cyclic shift:
for ( j= 1 ; j< i; j++ ) P[ j] = N- i+ j+ 1 ;
for ( j= i; j<= N; j++ ) P[ j] = j- i+ 1 ;
go( P) ;
// reversed cyclic shift:
reverse( P+ 1 ,P+ N+ 1 ) ;
go( P) ;
}
for ( i= 1 ; i+ 1 < maxn; i++ ) { // managing bignums
Count[ i+ 1 ] + = Count[ i] / an;
Count[ i] % = an;
}
outputTheAnswer( ) ;
return 0 ;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y2Fzc2VydD4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGNzdHJpbmc+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIG1heG4gMjIyMjIyMgojZGVmaW5lIGJhc2UxIDEwMDAwMDNMTAojZGVmaW5lIGJhc2UyIDIzOUxMCiNkZWZpbmUgbW9kMSAxMDAwMDAwMDA3TEwKI2RlZmluZSBtb2QyIDEwMDAwMDAwMDlMTAoKcGFpcjxsb25nIGxvbmcsbG9uZyBsb25nPmFbbWF4bl07CmludCBhbixpLGosTixLLGwscixsVCxrLGZbbWF4bl0sUFttYXhuXSx3YXNbbWF4bl0sY3ljbGVzLENvdW50W21heG5dLHEsY1ttYXhuXSxRW21heG5dLHNpemUsUlttYXhuXSxzW21heG5dOwpsb25nIGxvbmcgcHcxW21heG5dLHB3MlttYXhuXSxzaGExW21heG5dLHNoYTJbbWF4bl0scHcscmV0OwpjaGFyIFRbbWF4bl07CgpwYWlyPGxvbmcgbG9uZyxsb25nIGxvbmc+Z2V0aGFzaChpbnQgaixpbnQgeCl7IC8vIGhhc2ggb2YgYSBbajsgait4KSBzdWJzdHJpbmcKCXJldHVybiBtYWtlX3BhaXIoKChzaGExW2pdLXNoYTFbait4XSttb2QxKSpwdzFbal0pJW1vZDEsKChzaGEyW2pdLXNoYTJbait4XSttb2QyKSpwdzJbal0pJW1vZDIpOwp9Cgp2b2lkIGdldE9kZFN1YnBhbGluZHJvbWVzKCl7CS8vIE1hbmFjaGVyIGFsZ28gZm9yIGZpbmRpbmcgYWxsIG9kZCBzdWIgcGFsaW5kcm9tZXMuIG9uZSBjYW4gcHJvdmUgdGhhdCB0aGVyZSB3aWxsIGJlIG5vIG1vcmUgdGhhbiBOIGRpc3RpbmN0IHN1Y2ggcGFsaW5kcm9tZXMKCWZvcihpPTAsbD0wLHI9LTE7aTxsVDtpKyspewoJCWs9KGk+cj8wOm1pbihmW2wrci1pXSxyLWkpKSsxOwoJCXdoaWxlKGkrazxsVCYmaS1rPj0wJiZUW2kra109PVRbaS1rXSl7CgkJCWFbKythbl09Z2V0aGFzaChpLWssMiprKzEpOwoJCQkrK2s7CgkJfQoJCXdoaWxlKGkraz49bFR8fGktazwwfHxUW2kra10hPVRbaS1rXSktLWs7CgkJZltpXT1rOwoJCWFbKythbl09Z2V0aGFzaChpLWssMiprKzEpOwoJCWFbKythbl09Z2V0aGFzaChpLDEpOwoJCWlmKGkraz5yKWw9aS1rLHI9aStrOwoJfQp9Cgp2b2lkIGdldEV2ZW5TdWJwYWxpbmRyb21lcygpeyAvLyBNYW5hY2hlciBhbGdvIGZvciBmaW5kaW5nIGFsbCBldmVuIHN1YiBwYWxpbmRyb21lcy4gb25lIGNhbiBwcm92ZSB0aGF0IHRoZXJlIHdpbGwgYmUgbm8gbW9yZSB0aGFuIE4gZGlzdGluY3Qgc3VjaCBwYWxpbmRyb21lcwoJZm9yKGk9MDtpPGxUO2krKylmW2ldPTA7Cglmb3IoaT0wLGw9MCxyPS0xO2k8bFQ7aSsrKXsKCQlrPShpPnI/MDptaW4oZltsK3ItaSsxXSxyLWkrMSkpKzE7CgkJd2hpbGUoaStrLTE8bFQmJmktaz49MCYmVFtpLWtdPT1UW2kray0xXSl7CgkJCWFbKythbl09Z2V0aGFzaChpLWssMiprKTsKCQkJKytrOwoJCX0KCQlmW2ldPS0tazsKCQlpZihpK2stMT5yKWw9aS1rLHI9aStrLTE7Cgl9Cn0KCnZvaWQgYnVpbGRIYXNoKCl7IC8vIHByZXByb2Nlc3MgaGFzaGVzCglwdzFbMF09cHcyWzBdPTE7Cglmb3IoaT0xO2k8PWxUO2krKylwdzFbaV09KHB3MVtpLTFdKmJhc2UxKSVtb2QxLHB3MltpXT0ocHcyW2ktMV0qYmFzZTIpJW1vZDI7CglzaGExW2xULTFdPXNoYTJbbFQtMV09VFtsVC0xXTsKCWZvcihpPWxULTI7aSsxO2ktLSl7CgkJc2hhMVtpXT0oc2hhMVtpKzFdK3B3MVtsVC1pLTFdKlRbaV0pJW1vZDEsc2hhMltpXT0oc2hhMltpKzFdK3B3MltsVC1pLTFdKlRbaV0pJW1vZDI7Cgl9Cn0KCmxvbmcgbG9uZyBjYXJyeT0wOwppbnQgYm4sYlttYXhuXTsKCnZvaWQgb3V0cHV0VGhlQW5zd2VyKCl7CgljYXJyeT0wOwoJZm9yKGk9bWF4bi0xO2krMTtpLS0pewoJCWNhcnJ5PWNhcnJ5KmFuK0NvdW50W2ldOwoJCWlmKGNhcnJ5Pj1zaXplfHxibil7CgkJCWJbKytibl09Y2Fycnkvc2l6ZTsKCQkJY2FycnklPXNpemU7CgkJfQoJfQoJYXNzZXJ0KGNhcnJ5PT0wKTsKCWNbY1swXT0xXT0wOwoJZm9yKGk9MTtpPD1ibjtpKyspewoJCWZvcihqPTE7ajw9Y1swXTtqKyspY1tqXSo9YW47CgkJY1swXSs9MjAsY1sxXSs9YltpXTsKCQlmb3Ioaj0xO2o8PWNbMF07aisrKXsKCQkJY1tqKzFdKz1jW2pdLzEwOwoJCQljW2pdJT0xMDsKCQl9CgkJd2hpbGUoY1swXT4xJiZjW2NbMF1dPT0wKS0tY1swXTsKCX0KCWZvcihpPWNbMF07aTtpLS0pcHV0Y2hhcignMCcrY1tpXSk7CglwdXRzKCIiKTsKfQoKdmVjdG9yPGludD52ZWM7CnNldDx2ZWN0b3I8aW50PiA+UzsKCnZvaWQgZ28oaW50KkEpeyAvLyBjb3VudCB0aGUgbnVtYmVyIG9mIGN5Y2xlcyBpbiB0aGUgcGVybXV0YXRpb24KCWludCBpOwoJdmVjLmNsZWFyKCk7Cglmb3IoaT0xO2k8PU47aSsrKXZlYy5wdXNoX2JhY2soQVtpXSk7CglpZihTLmZpbmQodmVjKSE9Uy5lbmQoKSlyZXR1cm47IC8vIHVuaXF1ZWVuZXNzIGNoZWNraW5nIChtYXliZSwgaXQncyBub3QgbmVjZXNzYXJ5KQoJUy5pbnNlcnQodmVjKTsKCSsrc2l6ZTtjeWNsZXM9MDsKCWZvcihpPTE7aTw9TjtpKyspaWYod2FzW2ldIT1zaXplKXsKCQkrK2N5Y2xlczsKCQlmb3IocT1pO3dhc1txXSE9c2l6ZTtxPUFbcV0pd2FzW3FdPXNpemU7Cgl9CgkrK0NvdW50W2N5Y2xlc107Cn0KCmludCBtYWluIChpbnQgYXJnYywgY2hhciAqIGNvbnN0IGFyZ3ZbXSkgewoJZ2V0cyhUKTsKCWxUPXN0cmxlbihUKTsKCWJ1aWxkSGFzaCgpOwoJZ2V0T2RkU3VicGFsaW5kcm9tZXMoKTsKCWdldEV2ZW5TdWJwYWxpbmRyb21lcygpOwoJc29ydChhKzEsYSthbisxKTsKCWFuPXVuaXF1ZShhKzEsYSthbisxKS0oYSsxKTsKCWlmKGFuPT0xKXsgLy8gaWYgdGhlcmUncyBvbmx5IG9uZSBwYWxpbmRyb21lICg8PT4gfFR8PTEpCgkJY291dDw8MTw8ZW5kbDsKCQlyZXR1cm4gMDsKCX0KCXNjYW5mKCIlZCIsJk4pOwoJZm9yKGk9MTtpPD1OO2krKyl7IC8vIGdlbmVyYXRpbmcgYWxsIHJlYWNoYWJsZSBwZXJtdXRhdGlvbnMKCQkvLyBjeWNsaWMgc2hpZnQ6CgkJZm9yKGo9MTtqPGk7aisrKVBbal09Ti1pK2orMTsgCgkJZm9yKGo9aTtqPD1OO2orKylQW2pdPWotaSsxOwoJCWdvKFApOwoJCS8vIHJldmVyc2VkIGN5Y2xpYyBzaGlmdDoKCQlyZXZlcnNlKFArMSxQK04rMSk7CgkJZ28oUCk7Cgl9Cglmb3IoaT0xO2krMTxtYXhuO2krKyl7IC8vIG1hbmFnaW5nIGJpZ251bXMKCQlDb3VudFtpKzFdKz1Db3VudFtpXS9hbjsKCQlDb3VudFtpXSU9YW47Cgl9CglvdXRwdXRUaGVBbnN3ZXIoKTsKICAgIHJldHVybiAwOwp9Cg==