Migrated from Lutece 2820 茴纹窜

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

ljj 很喜欢回文串，他觉得对称的东西很优美（很符合他的强迫症），但最近他对茴纹窜很感兴趣。

茴纹窜是这样构造的：首先要已知一个母串 S，然后在串 S 中任意插入 n 个字符（可以在 S 串前面或者后面插入字符），构成一个新的串 T，如果 T 是一个回文串，那么我们称串 T 是一个关于母串 S 和参数 n 的茴纹窜。

现在给定一个串 S，给定插入字符的数量 n ，现在求有多少种关于 S 和 n 的茴纹窜，对结果取模 $10^{9}+7$

注意本题中所有串的字符只包含小写英文字母。

Input

第一行读入一个字符串 S

第二行读入一个数 n ，表示插入的字符数量

Output

输出一个整数，表示茴纹窜的数量

Samples

acmmmc
1

1

ccf
2

28

icpcccpc
15

686940811

uestccestu
20

323696423

Constraints

串长$|S|\le 200,n\le 10^{9}$

Note

本题略卡常，请注意程序常数

Resources

2022 UESTC ICPC Training for String and Search Algorithm