Problem Statement

A finite automaton is a mathematical object that consists of the following components:

• Alphabet A. This is simply a set of characters.
• Set of states S. One of the states is called starting and some of the states are called accepting.
• Transition function F. For each state i from S and for each character j from A the result of this function is some state F(i, j) from S.

For each string composed of alphabet characters, an automaton either accepts or rejects it. This is done as follows. First, the automaton is set to its starting state. Then it subsequently reads all the characters from the given string. For each character c it reads, the automaton's state is changed to F(cur, c), where cur is the automaton's state immediately before reading this character. After all characters are read, the automaton checks its final state. If it is accepting, then the string is accepted, otherwise it is rejected.

You are given a String[] transitions describing a finite automaton. The number of elements in transitions is the number of states in the automaton. States are denoted by consecutive uppercase letters starting from 'A'. The first state is the starting state and the last state is the only accepting state. The input alphabet consists of consecutive lowercase letters starting from 'a', and the size of the alphabet is equal to the length of transitions[0].

The transition function is defined as follows. From the i-th state (where state 0 is 'A'), the j-th symbol (where symbol 0 is 'a') will lead to the X-th state, where X = transitions[i][j].

First, the automaton is given an input string of length stringLength consisting entirely of 'a' symbols. The automaton either accepts or rejects the string. Then, the following happens modifications times. One of the symbols in the input string is modified, the automaton is reset to its starting state, and it is then given the new input string, which it either accepts or rejects.

To generate the sequence of modifications you should generate arrays x and c using the following code:

int initElements = length(x0);
int letters = length(transitions[0]);

for (int i = 0; i < initElements; i++) {
	x[i] = x0[i] mod stringLength;
	c[i] = c0[i] mod letters;
}

for (int i = initElements; i < modifications; i++) {
	x[i] = 0;
	c[i] = 0;	
	for (int j = i - initElements; j < i; j++) {
		x[i] = (x[i] + xa[j - i + initElements] * x[j]) mod stringLength;
		c[i] = (c[i] + ca[j - i + initElements] * c[j]) mod letters;
	}
}

The i-th element of the array x is the position where the i-th modification occurs. The symbol at position x[i] of the string should be modified to the c[i]-th symbol of the alphabet (where symbol 0 is 'a'). All indices are 0-based.

Return the number of times the automaton accepts a string.

Definition

Constraints

Examples