Number of Routings

All submissions for this problem are available.
It is well known that the routing algorithm used on the Internet is highly nonoptimal. 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: ![11](https://i.imgur.com/dYfZeGz.jpg "Figure") 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$. ###Input: 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 $i^{th}$ integer on line $j$ is the number of links connecting node $i$ with node $j$. (The $i^{th}$ entry on line $j$ will be the same as the $j^{th}$ entry on line $i$. Further, the $i^{th}$ 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. ###Output: A single integer indicating the number of routings from $S$ to $T$ with $K$ hops modulo $42373$. ###Constraints:  $1 \leq N \leq 70$.  $1 \leq K \leq 10^9$. ###Sample Input 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 ###Sample Output 7Author:  admin2 
Date Added:  17092018 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions