Pinguos are funny little monsters. Actually, there exist N different types of Pinguos (for simplicity numbered from 1 to N). Each midnight, each Pinguo dies. When a Pinguo dies, it gives birth to one or more new Pinguos. The types and numbers of these new Pinguos are uniquely determined by the type of the old, now dead, Pinguo. Please note that the total count of Pinguos never decreases, as each old Pinguo is replaced by at least one new Pinguo.
You are given a String[] **transforms** (containing N elements) describing for each type of Pinguo what types of Pinguos will arise from its dead body. For each i between 1 and N, element i-1 of **transforms** is a String containing a space-separated list of integers. These integers are the types of Pinguos that will arise from a dead Pinguo of type i. For example, if **transforms**[6] is "2 3 3", it means that when a Pinguo of type 7 dies, one Pinguo of type 2 and two Pinguos of type 3 will arise.
It is not hard to see that sometimes the number of Pinguos will grow towards infinity, eventually exceeding all bounds. However, there are some cases in which the number of Pinguos reaches a finite constant and then stays the same forever. (Note that these are the only two possible cases, as the total number of Pinguos never decreases. Also note that in the second case only the total number of Pinguos remains constant, their types may be changing every day.)
Initially you have a single Pinguo of type 1. You want to know what is the final (finite) number of Pinguos you will eventually end up with. Return this number modulo 1,000,000,007. If the count of Pinguos grows beyond all bounds, return -1 instead. |