Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Alien Neural Network

Limits: 2s, 512 MB

The great researcher Dr. Bari loves to do research (Obviously!!). He recently discovered a parallel universe. Now he wants to communicate with the aliens in the parallel universe.

Dr. Bari loves Deep Learning, and suddenly he comes up with a novel architecture of neural network which could be used to communicate with the aliens.

A neural network is a mathematical model that has taken inspiration from the human brain. Neural networks are organized in layers. Usually, a neural network has one input layer, at least one or more hidden layers and an output layer. Each layer has some nodes, that take input from the nodes of the previous layer. These nodes then provide output for the next layer. Inputs are given in the first layer and outputs are produced in the final layer. Each node in any of the layers produces its output from its input. Nodes use a function called activation function to produce this output.

In Figure 1, a typical neural network architecture with 2 hidden layers is shown. Here, all the nodes (the circles) of a layer are connected with all the nodes in the next layer. This type of layers in a neural network are called fully connected layer. Also, since it has no cycles, it is called as Feedforward Neural Network.

Dr. Bari will give his input text to the neural network, the neural network will then translate his input text to the language of the aliens. Since Dr. Bari is using this feed forward neural network to communicate with aliens in another parallel universe, he deployed his model in a server located in the parallel universe. And thus, each edge in the neural network is replaced by the whole network and his usual neural network becomes an “alien neural network”.

As each edge of the network is replaced by the whole network, Dr. Bari has decided to design his neural network with less complexity (see Figure 2). Thus, in the input layer, there will be only one node. Also, in the hidden layers, all the nodes of the previous layer may not be connected with all the nodes in the current layer. There can have some skip connections too. Which means some nodes of a layer (L = l) may not have connection with the nodes of the immediate next layer (L = l+1), rather those nodes (L = l) can have direct connections with nodes of any of the next layers (L > l+1).

In this problem, you don’t need to calculate the activation function. Since the contest is just five hours long, you cannot train a neural network model within a very short time! Dr. Bari has assigned you to help him in his research. He does not want to lose any information. So you need to calculate the maximum amount of information that can flow from the input node to the output node in the “alien neural net”.

Dr. Bari defined his Alien Neural Network formally as follows:

Let, G0 = (V0, E0) be a directed graph with the set of vertices, V0 and set of edges, E0. Each edge in the set E0 has a capacity of information flow associated with it. Two nodes s, t ∈ V0 are also defined as input and output node respectively. So, E0 ∈ (V0 x V0 x ℕ). Now, first extension of G0 is a graph G1 defined as follows:

For each edge (u, v, c) ∈ E0: remove the edge and insert the whole graph G0 considering u as s and v as t.

So, we can define ith extension of G0 as first extension of Gi-1, Gi as following:

For each edge (u, v, c) ∈ Ei-1: remove the edge and insert the whole graph Gi-1 considering u as s and v as t.

Now, as you can see, we are increasing the number of nodes and edges on each transformation, but the nodes from the previous graph are always preserved. Thus, we say that input and output node defined for graph G0 is preserved in any following transformation i > 0.

Given the graph G0 as a set of edges and the input and output nodes and an integer N, calculate the maximum amount of information flow of the graph GN. To better understand this graph transformation, check the notes section.

Input

Input begins with the integer number of test cases to be followed, T (0 < T < 101). Each test case will begin with five integers representing the number of nodes in G0, |V0| (2 ≤ |V0| ≤ 1000), number of edges in G0, |E0| (1 ≤ |E0| ≤ 10000), the number N for Nth extension GN (0 ≤ N ≤ 1016), and finally two integer s and t for input and output node (0 ≤ s, t < |V0|). Then |E0| line follows. Each of the next |E0| lines containing three integers u, v, c (0 ≤ u, v < |V0| and 0 < c ≤ 109).

Output

For each case print, the case number and the maximum amount of information flow of the graph GN as described in the problem modulo 109+7.

Samples

InputOutput
3
3 2 100 0 2
0 1 10
1 2 20
4 4 0 0 3
0 1 2
1 3 3
0 2 2
2 3 3
3 3 50 0 2
0 2 3
0 1 4
1 2 4
Case 1: 10
Case 2: 4
Case 3: 384884644

Let, G0 be:

here, let’s consider (s, t) = (0, 1)

So, G1 is:

Another Example:

Let G0 be:

Considering (s, t) = (0,2)

Then, G1 will be:

Yet another example:

Let G0 be:

Considering (s, t) = (0, 2)

G1 will be:

Author
Discussion
Submit

Login to submit