#P18498. Anton's ABCD

Anton's ABCD

Anton's ABCD

众所周知,Anton Trygub 喜欢出只包含字符 ABC 的字符串题,尤其喜欢允许对字符串进行操作的题目。为了向他致敬,并进一步扩展这类问题,这次给你一个只包含字符 ABCD 的字符串。

你可以执行以下操作零次或任意多次:

  • 选择一个长度恰好为 44、并且是 ABCD 的循环移位的子串,将这个子串向左或向右循环移动 一位。

这里允许选取的子串是 ABCD、BCDA、CDAB、DABC 四种。例如,ABCD 向左循环移动一位成为 BCDA,向右一位成为 DABC。其它字符保持原位置;只有满足上述条件的长度 44 子串才能操作。

求从给定字符串出发,通过上述操作能够得到多少个不同的字符串。零次操作得到的原串也计入。由于答案可能很大,输出对 109+710^9+7 取模的结果。

输入格式

输入只有一行,一个字符串 SS,满足 1≤∣S∣≤20001\le |S|\le 2000,且仅包含大写字符 A、B、C、D。输入没有单独的长度整数。

输出格式

输出一行一个整数,表示能够得到的不同字符串数量,对 109+710^9+7 取模。

原样例 1

DABC
4

此时整个字符串就是 ABCD 的一个循环移位。最多执行两次操作,就能得到全部四种循环移位。

原样例 2

AABBCCDD
1

一开始没有任何合法操作,所以只能得到原字符串。

原样例 3

ABCDABCD
52