Problem 2: Number of Routings, (K Narayan Kumar, CMI)
It is well known that the routing algorithm used on the Internet is highly non-optimal. A "hop", in Internet jargon, is a pair of nodes that are directly connected - by a cable or a microwave link or whatever. The number of hops that a packet may take in going from one node to another may be far more than the minimum required.
But the routing algorithm used by the Siruseri Network company is worse. Here, a packet sent from one node to another could even go through the same node twice or even traverse the same hop twice before it eventually finds its way to its destination. Sometimes a packet even goes through the destination more than once before it is considered "delivered". Suppose the network in Siruseri consisted of the following nodes and cables:
There are 5 nodes and 8 cable links. Note that a pair of nodes may be connected by more than one link. These are considered to be different hops. All links are bidirectional. A packet from node 1 to node 5 may, for example, travel as follows: 1 to 2, 2 to 1, 1 to 3, 3 to 2, 2 to 1, 1 to 4, 4 to 5, 5 to 4, 4 to 5. This routing is of length 9 (the number of hops is the length of a given routing). We are interested in counting the number of different routings from a given source to a target that are of a given length.
For example, the number of routings from 1 to 2 of length 3 are 7. They are as follows (separated by ;): 1 to 2, 2 to 1 and 1 to 2; 1 to 3, 3 to 1 and 1 to 2; 1 to 4, 4 to 1 and 1 to 2; 1 to 5, 5 to 1 and 1 to 2; 1 to 4, 4 to 3 (via the left cable) and 3 to 2; 1 to 4, 4 to 3 (via the right cable) and 3 to 2; 1 to 2, 2 to 3 and 3 to 2.
You will be given a description of the network at Siruseri as well as a source, a target and the number of hops, and your task is to determine the number of routings from the source to the target which have the given number of hops. The answer is to be reported modulo 42373.
The first line of the input consists of a single integer N indicating the number of nodes in the Siruseri. This is followed by N lines each containing N positive integers. The ith integer on line j is the number of links connecting node i with node j. (The ith entry on line j will be the same as the jth entry on line i. Further, the ith entry on line i will always be 0. ) This is followed by a line with 3 integers S, T and K, the source, the target and the number of hops.
A single integer indicating the number of routings from S to T with K hops modulo 42373.
You may assume that N ≤ 70 and K ≤ 109.
Here is the sample input and output corresponding to the example discussed above.
5 0 1 1 1 1 1 0 1 0 0 1 1 0 2 0 1 0 2 0 1 1 0 0 1 0 1 2 3