#P18498. Anton's ABCD
Anton's ABCD
Anton's ABCD
众所周知,Anton Trygub 喜欢出只包含字符 ABC 的字符串题,尤其喜欢允许对字符串进行操作的题目。为了向他致敬,并进一步扩展这类问题,这次给你一个只包含字符 ABCD 的字符串。
你可以执行以下操作零次或任意多次:
- 选择一个长度恰好为 、并且是
ABCD的循环移位的子串,将这个子串向左或向右循环移动 一位。
这里允许选取的子串是 ABCD、BCDA、CDAB、DABC 四种。例如,ABCD 向左循环移动一位成为 BCDA,向右一位成为 DABC。其它字符保持原位置;只有满足上述条件的长度 子串才能操作。
求从给定字符串出发,通过上述操作能够得到多少个不同的字符串。零次操作得到的原串也计入。由于答案可能很大,输出对 取模的结果。
输入格式
输入只有一行,一个字符串 ,满足 ,且仅包含大写字符 A、B、C、D。输入没有单独的长度整数。
输出格式
输出一行一个整数,表示能够得到的不同字符串数量,对 取模。
原样例 1
DABC
4
此时整个字符串就是 ABCD 的一个循环移位。最多执行两次操作,就能得到全部四种循环移位。
原样例 2
AABBCCDD
1
一开始没有任何合法操作,所以只能得到原字符串。
原样例 3
ABCDABCD
52