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 nn cells. Each cell contains exactly one small English letter. You also are given a word ww , which consists of kk small English letters. A solution of the puzzle is a sequence of field cells c1c_{1} , ...... , ckc_{k} , such that:

  • For all ii from 11 to kk the letter written in the cell cic_{i} matches the letter wiw_{i} ;
  • All the cells in the sequence are pairwise distinct;
  • For all ii from 11 to k1k-1 cells cic_{i} and ci+1c_{i+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+710^{9}+7 .

Two solutions cic_{i} and cic'_{i} are considered distinct if the sequences of cells do not match in at least one position, that is there is such jj in range from 11 to kk , such that cjcjc_{j}≠c'_{j} .

输入格式

The first two lines contain the state of the field for the puzzle. Each of these non-empty lines contains exactly nn small English letters.

The next line is left empty.

The next line is non-empty and contains word ww , consisting of small English letters.

The length of each line doesn't exceed 20002000 .

输出格式

Print a single integer — the number of distinct solutions for the puzzle modulo 109+710^{9}+7 .

输入输出样例

  • 输入#1

    code
    edoc
    
    code
    

    输出#1

    4
    
  • 输入#2

    aaa
    aaa
    
    aa
    

    输出#2

    14
    
首页