该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

本题采用文件读写评测，输入输出流重定向到cipher.in/out

题目描述

特工兔和兔老大之间的电报必须加密，用大写英文字母编写密令。一个密令可以为空，也可以由若干个字符 A 到 Z 组成。

现在给定一个长度为 $n$ 的密令 $S$。兔老大希望设计一个长度恰好为 $2n$ 的新密令 $T$ 作为备份，并要求：

1. $T$ 是回文串，即从左向右和从右向左读完全相同；
2. $S$ 是 $T$ 的子序列。

如果可以从 $T$ 中删除若干个字符（也可以一个都不删除），使剩余字符按照原来的相对顺序组成 $S$，则称 $S$ 是 $T$ 的子序列。被删除的字符不要求连续。

请求出满足条件的不同密令 $T$ 的数量。

输入格式

第一行包含一个整数 $n$，表示密令 $S$ 的长度。

第二行包含一个长度为 $n$ 的字符串 $S$，其中每个字符均为大写英文字母。当 $n=0$ 时，第二行为空行。

输出格式

输出一个整数，表示满足条件的不同回文密令数量对 $10^9+7$ 取模后的结果。

2
AA

51

2
AB

2

数据范围

对于所有测试数据，保证 $0\le n\le 200$，$|S|=n$，且 $S$ 仅由大写英文字母组成。