CF613E.Puzzle Lover
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Oleg Petrov loves crossword puzzles and every Thursday he buys his favorite magazine with crosswords and other word puzzles. In the last magazine Oleg found a curious puzzle, and the magazine promised a valuable prize for it's solution. We give a formal description of the problem below.
The puzzle field consists of two rows, each row contains n cells. Each cell contains exactly one small English letter. You also are given a word w , which consists of k small English letters. A solution of the puzzle is a sequence of field cells c1 , ... , ck , such that:
- For all i from 1 to k the letter written in the cell ci matches the letter wi ;
- All the cells in the sequence are pairwise distinct;
- For all i from 1 to k−1 cells ci and ci+1 have a common side.
Oleg Petrov quickly found a solution for the puzzle. Now he wonders, how many distinct solutions are there for this puzzle. Oleg Petrov doesn't like too large numbers, so calculate the answer modulo 109+7 .
Two solutions ci and ci′ are considered distinct if the sequences of cells do not match in at least one position, that is there is such j in range from 1 to k , such that cj=cj′ .
输入格式
The first two lines contain the state of the field for the puzzle. Each of these non-empty lines contains exactly n small English letters.
The next line is left empty.
The next line is non-empty and contains word w , consisting of small English letters.
The length of each line doesn't exceed 2000 .
输出格式
Print a single integer — the number of distinct solutions for the puzzle modulo 109+7 .
输入输出样例
输入#1
code edoc code
输出#1
4
输入#2
aaa aaa aa
输出#2
14