f(X) = A + X + B + X + C

Count occurrences of pattern F in the K-fold string expansion f(X)=A+X+B+X+C applied to S, modulo 1e9+7.

Hard8String matchingDynamic programmingMatrixStringNo attempts yetTime limit2sMemory limit512 MB

Description

Examples4

Problem

A function $f$ takes a string $X$ and returns $f(X) = A + X + B + X + C$ , where $+$ is string concatenation and $A$ , $B$ , $C$ are fixed non-empty strings.

Repeated application is defined by $f^1(X) = f(X)$ and $f^K(X) = f(f^{K-1}(X))$ .

You are given strings $A$ , $B$ , $C$ , $S$ , $F$ and an integer $K$ . Count how many times $F$ occurs as a substring of $f^K(S)$ . Occurrences that start at different positions are counted separately, even when they overlap.

Input

The first line contains $A$ , $B$ , $C$ , $S$ , $F$ and $K$ , separated by spaces. $A$ , $B$ , $C$ , $S$ and $F$ are strings of lowercase letters whose length is between 1 and 50. $K$ is a natural number not greater than 10,000,000.

Output

Print the number of occurrences of $F$ as a substring of $f^K(S)$ , modulo 1,000,000,007.