CF506E.Mr. Kitayuta's Gift

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Kitayuta 先生送给你一个由小写英文字母组成的字符串 $s$ 。你需要向 $s$ 中恰好插入 $n$ 个小写英文字母，使该字符串变为一个回文串（回文串是指正着读和反着读都相同的字符串，例如 "noon"、"testset" 和 "a" 都是回文串，而 "test" 和 "kitayuta" 不是）。你可以选择任意 $n$ 个小写英文字母，将它们插入到 $s$ 的任意位置（包括开头和结尾）。

即使插入少于 $n$ 个字母也可以使 $s$ 变为回文串，你也必须恰好插入 $n$ 个字母。

请计算通过这种方式可以得到多少种不同的回文串，对 $10007$ 取模。

输入格式

第一行包含一个字符串 $s$ ，满足 $1 \leq |s| \leq 200$ 。 $s$ 中每个字符都是小写英文字母。

第二行包含一个整数 $n$ ，满足 $1 \leq n \leq 10^{9}$ 。

输出格式

输出通过插入恰好 $n$ 个小写英文字母能够得到的不同回文串数量，对 $10007$ 取模。

输入输出样例

输入#1
```
revive
1
```
输出#1
```
1
```
输入#2
```
add
2
```
输出#2
```
28
```

说明/提示

对于第一个样例，你可以通过在 "revive" 末尾插入字母 'r' 得到回文串 "reviver"。

对于第二个样例，可以得到以下 28 个回文串："adada"、"adbda"、...、"adzda"、"dadad" 和 "ddadd"。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页