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₀, a₁, a₂,..., a₁₀₀₀₀} 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₁, F₂, F₃, ... ) associated with (a, b, c, d) by the equations:
1. F₁ = 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₁t₂t₃...t_N be text and P =p₁p₂p₃...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⁶; 1 ≤ M ≤ 100; 1 ≤ A1, A2, B, C, D ≤ 10⁹; 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 4

Output:

15

Let us suppose that for alphabet A holds a₀ = 'a', a₁ = 'b', a₂ = 'c', a₃ = '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 3

Output:

9

Let us suppose that for alphabet A holds a₀ = 'a', a₁ = 'b', a₂ = '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 8

Output:

232