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 = {a0, a1, a2,..., a10000} consists of 10001 characters, each character ak 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 = (F1, F2, F3, ... ) associated with (a, b, c, d) by the equations:
1. F1 = a,
2. Fj = ((Fj−1+1) × b + c) mod d, for j > 1.


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 = t1t2t3...tN be text and P =p1p2p3...pM 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 ti (1 ≤ i ≤ N ) is equal to the value (Fi mod E), where Fi is the i-th element of the sequence associated with 4-tuple (A1, B, C, D).
The alphabet index of the pattern character pj (1 ≤ j ≤ M) is equal to the value (Fj mod E), where Fj 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×106; 1 ≤ M ≤ 100; 1 ≤ A1, A2, B, C, D ≤ 109; 1≤ E ≤ 5000.


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

12 4   3 1041   754143 530009 1056511 4
Let us suppose that for alphabet A holds a0 = 'a', a1 = 'b', a2 = 'c', a3 = '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

7 4  1 2  754043 500009 1056513 3
Let us suppose that for alphabet A holds a0 = 'a', a1 = 'b', a2 = '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

100000 100   25 135   751043 501019 1056513 8