Non Absorbing DFA

Time Limit: 5 Seconds
Memory Limit: 32768 KB

In the theory of compilers and languages *finite state machines*, also known as *finite automata* are
widely used. Deterministic finite automation (DFA) is an ordered set *<Z, U, s, T, F>* where *Z* is the finite
set called input alphabet, *U* is the finite set of states, *s* (belongs to *U*) is the *initial state*, *T* (is a subset of *U*) is the set of *terminal
states* and *F : U * Z -> U* is the *transition function.*

The input of the automation is the string *z* over *Z*. Initially the automation is in state *s*. Each step
it reads the first character *c* of the input string and changes its state to *F(u, c)* where u is the current
state. After that the first character of the input string is removed and the step repeats. If when its input
string is empty the automation is in the terminal state, it is said that it accepts the initial string *z*, in
the other case it *rejects* it.

In some cases to simplify the automation the concept of *nonabsorbing edges* is introduced. That is,
in addition to *F* the function *G : U * Z -> {0, 1}* is introduced and when making a transition from some
state *u* with some character *c*, the leading character is removed from the input string only if *G(u, c) = 0*.
If *G(u, c) = 1*, the input string is kept intact and next transition is performed with the new state and the
same character.

It is said that such automation accepts some string *z* if after a number of steps it transits to the
terminal state and the input string becomes empty.

Your task is given the DFA with nonabsorbing edges to compute the number of strings of the given
length *N* that it accepts.

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

**Input**

The first line of the input file contains *Z* - a subset of the English alphabet, several different small
letters. Next line contains *K = |U|* - the number of states of the automation (1 <= *K* <= 1000). Let
states be numbered from 1 to *K*. Next line contains *S* (1 <= *S* <= *K*) - the initial state, followed by
*L = |T|* - the number of terminal states and then *L* different integer numbers ranging from 1 to *K* -
the numbers of terminal states.

Next *K* lines contain |Z| integer numbers each and define *F*. Next *K* lines define *G* in a similar way.
The last line of the input file contains *N*(1 <= *N* <= 60).

**Output**

Output the only number - the number of different strings of length *N* over *Z* that the given DFA
accepts.

**Sample Input**

1

ab

2

1 1 2

2 1

1 2

0 1

0 0

3

**Sample Output**

2

In the given example the two strings accepted by the automation are ��aaa�� and ��abb��.

Author:

**Andrew Stankevich**
Source:

**Andrew Stankevich's Contest #2**
Submit
Status