- Correct output – H1
- Correct output – H2
- C++ program solving both data sets
- bc program solving both data sets

The most simple way how to compute the output was to simulate the bacteria expansion step-by-step. If your programming language doesn't support long numbers, you had to implement some simple arithmetical operations with them on your own. This solution worked for the easy input file. Unfortunately, it is too slow to solve the hard input.

Yes, but is there a way to do something better than a plain simulation?
Let's imagine the array of colonies as a vector. Each of the changes
that could be applied to the colonies is in fact some linear transformation.
We may describe each of the operations using a square (**NxN**) matrix.
To apply the change now means to multiply the vector containing the
numbers of bacteria by the corresponding matrix.

If you don't understand the terms *vector* and *matrix*, please consult
some book on basic algebra or an online resource such as
MathWorld.
The only things you need to know for the purpose of this task are: what is a vector,
what is a matrix and how to multiply them. If you do understand these terms but are
unfamiliar with their usage, you may want to look at a simple example at the end of
this solution before proceeding.

If we had **5** colonies, matrices for some of the changes would look as follows:

die30

1 | 0 | 0 | 0 | 0 |

0 | 1 | 0 | 0 | 0 |

0 | 0 | 1 | 0 | 0 |

0 | 0 | 0 | 0 | 0 |

0 | 0 | 0 | 0 | 1 |

reproduce25

1 | 0 | 0 | 0 | 0 |

0 | 1 | 0 | 0 | 0 |

0 | 0 | 5 | 0 | 0 |

0 | 0 | 0 | 1 | 0 |

0 | 0 | 0 | 0 | 1 |

copy13

1 | 0 | 0 | 0 | 0 |

0 | 1 | 0 | 0 | 0 |

0 | 0 | 1 | 0 | 0 |

0 | 1 | 0 | 1 | 0 |

0 | 0 | 0 | 0 | 1 |

teleport24

1 | 0 | 0 | 0 | 0 |

0 | 1 | 0 | 0 | 0 |

0 | 0 | 1 | 0 | 0 |

0 | 0 | 0 | 1 | 0 |

0 | 0 | 1 | 0 | 0 |

swap02

0 | 0 | 1 | 0 | 0 |

0 | 1 | 0 | 0 | 0 |

1 | 0 | 0 | 0 | 0 |

0 | 0 | 0 | 1 | 0 |

0 | 0 | 0 | 0 | 1 |

merry-go-round 0 0

0 | 1 | 0 | 0 | 0 |

0 | 0 | 1 | 0 | 0 |

0 | 0 | 0 | 1 | 0 |

0 | 0 | 0 | 0 | 1 |

1 | 0 | 0 | 0 | 0 |

Assume that **X _{1}**,

So far we were silently ignoring the fact that we have to
compute everything modulo **K**. We will keep on ignoring this fact.
Just note that this doesn't affect the linearity of the operations
(read: doesn't cause any problems).

We now have to compute the vector
**(1, 1, ..., 1) * X ^{t} * X_{1} * X_{2} * ... * X_{r}**
effectively.
Let

The time complexity of a simple simulating algorithm is **O(NT)**.
What about the second algorithm? The cost of multiplying two matrices is **O(N ^{3})**.
We need

**Hint:** As you maybe noticed, **K** in both input files is the same. Its last digits
are: ...2890625. Yes, it is a power of 5, namely **K = 5 ^{96}**. If you noticed
this you could internally represent all the big numbers in base 5 (instead of base 10) and then
you could do all computations modulo

For those of you unfamiliar with algebra a simple example. Let **F ^{i}**
be the famous Fibonacci numbers.
(

0 | 1 |

1 | 1 |

Now suppose we start with the vector **(0,1)**. After we multiply it by **A** **n**
times, we get the vector **(F ^{n},F^{n+1})**. Matrix multiplication is
associative (but not commutative!), therefore multiplying a vector