## Dictionary automaton

Let A be a finite alphabet and let Y be a finite set of unempty strings over A and let*u*,

*v*be strings over A. Note that the set Y is also a language over A.

Let us denote the Levenshtein distance between

*u*and

*v*by the symbol LD(

*u*,

*v*).

Let us denote by symbol minLD(

*u*, Y) the minimum value of the set {LD(

*u*,

*w*) |

*w*∈ Y }.

In this problem we define the

**dictionary automaton**DA(Y) as follows:

1. DA(Y) is a NFA over alphabet A accepting Y.

2. The transition diagram of DA(Y) is a rooted tree in which vertices represent states of DA(Y) and the edges represent transitions between the states. The root of the tree represents the start state of DA(Y).

3. The number of states of DA(Y) is minimum possible.

We remind you that the rooted tree is a directed weakly connected acyclic graph in which there is a single root node and the in-degree of each node distinct from the root node is 1.

Note that each leaf of the transition diagram of DA(Y) represents a final state of DA(Y) and that there may be more final states in DA(Y) than there are leaves in its transition diagram.

**The task**

Let text T and pattern P be unempty strings over alpahabet A, let US(T) be the set of all unempty substrings of T.

Let us define set S(T, P) as a set of all unempty substrings

*w*of T for which holds LD(

*w*, P) = minLD(P, US(T)).

We have to find the number of states of the automaton DA(S(T, P)).

We supose that the alphabet A = {

*a*

_{0},

*a*

_{1},

*a*

_{2},...,

*a*

_{10000}} consists of 10001 characters, each character

*a*

_{k}is uniquely identified by its alphabet index

*k*, 0 ≤

*k*≤ 10000.

For any integer 4-tuple (

*a*,

*b*,

*c*,

*d*) we define an infinite integer

**sequence**

*F*= (

*F*

_{1},

*F*

_{2},

*F*

_{3}, ... )

**associated with**(

*a*,

*b*,

*c*,

*d*) by the equations:

1.

*F*

_{1}=

*a*,

2.

*F*

_{j}= ((

*F*

_{j−1}+1) ×

*b*+

*c*) mod

*d*, for

*j*> 1.

### Input

The input contains one text line with eight integers N, M, A1, A2, B, C, D, E written in this order and separated by at least one space.Let T =

*t*

_{1}

*t*

_{2}

*t*

_{3}...

*t*

_{N}be text and P =

*p*

_{1}

*p*

_{2}

*p*

_{3}...

*p*

_{M}be the pattern. The input defines T and P as follows:

Value N represents length of text T, value M represents length of pattern P.

The alphabet index of the text character

*t*

_{i}(1 ≤

*i*≤ N ) is equal to the value (

*F*

_{i}mod E), where

*F*

_{i}is the

*i*-th element of the sequence associated with 4-tuple (A1, B, C, D).

The alphabet index of the pattern character

*p*

_{j}(1 ≤

*j*≤ M) is equal to the value (

*F*′

_{j}mod E), where

*F*′

_{j}is the

*j*-th element of the sequence associated with 4-tuple (A2, B, C, D).

The following bounds hold for the input values:

1 ≤ N ≤ 5×10

^{6}; 1 ≤ M ≤ 100; 1 ≤ A1, A2, B, C, D ≤ 10

^{9}; 1≤ E ≤ 5000.

### Output

The output contains single text line with one integer representing the number of states of the dictionary automaton DA(S(T,P)) which recognizes the language of all such unempty substrings of the text T which Levenshtein distance form pattern P is minimum possible, see the definitions above.### Example 1

Input:12 4 3 1041 754143 530009 1056511 4Output:

15Let us suppose that for alphabet A holds

*a*

_{0}= '

`a`

', *a*

_{1}= '

`b`

', *a*

_{2}= '

`c`

', *a*

_{3}= '

`d`

'. Then T = `daaccbcbddad`

, P = `bdab`

.The value of minLD(P, US(T)) is 2.

The sequence

*F*is:

3, 377048, 23476, 533882, 993310, 16641, 683646, 270129, 727579, 906099, 374240, 694487, ...

The characters of T are

3, 0, 0, 2, 2, 1, 2, 1, 3, 3, 0, 3.

The sequence

*F*′ is:

1041, 302831, 575692, 141345, ...

The characters of P are

1, 3, 0, 1.

The resulting dictionary automaton is depicted in the picture bellow, each state except for the start state S is labeled by the character associated with the transition which ends in that state:

### Example 2

Input:7 4 1 2 754043 500009 1056513 3Output:

9Let us suppose that for alphabet A holds

*a*

_{0}= '

`a`

', *a*

_{1}= '

`b`

', *a*

_{2}= '

`c`

'. Then T = `bababab`

, P = `cccc`

and the dictionary recognized by the dictionary automaton DA(S(T,P)) is {`a`

, `ab`

, `aba`

, `abab`

, `b`

, `ba`

, `bab`

, `baba`

}.
### Example 3

Input:100000 100 25 135 751043 501019 1056513 8Output:

232