This page is still under construction.

Parts of this page are still being built. What you see may change.

Working Cells

Time limit1sMemory limit512 MB

Summary
Given T periodic N-vertex weighted digraphs, count modulo 1e9+7 the number of D-step walks from every hub i to every hub j.
Level

Hard9 of 10

Topics
Matrix, Divide and conquer, Graph, Dynamic programming
Solved
No attempts yet

Problem

The human body contains about 37 trillion cells. They are hard at work inside the body today as well. Among them, red blood cells travel through blood vessels and play an important role carrying oxygen and nutrients.

Red blood cells move between hubs such as the heart and lungs, transporting oxygen and nutrients. The body has N hubs in total, and some hubs are connected to each other by passages. Traversing a passage between hubs takes 1 second. However, because blood vessels have valves and sections under construction in various places, the connections between hubs change every second. Even so, every part of the body needs oxygen and nutrients, so a red blood cell cannot stay still and must take exactly one passage every second. Some passages may have the same starting hub and ending hub. At certain moments, some hubs may have no outgoing passage; in that case, the cell is destroyed 1 second after arriving and becomes one with the body again. Cruel, but that is how our body works.

Our red blood cell wanders through the blood vessel map that changes every moment, but it still does its best and works hard day after day. A white blood cell nearby saw the red blood cell wandering and wanted to help.

Through tens of hours of wandering, the white blood cell learned that the blood vessel map of the body repeats with a period of T seconds. It wants to use this fact to compute, for every ordered pair of hubs, the number of ways the red blood cell can start at hub A and reach hub B exactly D seconds later, but it is too single-celled and not smart enough to do the calculation. A path is defined as the sequence of passages traversed during D seconds. Help the white blood cell compute the number of ways the red blood cell can move from one hub to another during D seconds!

Input

The first line contains the period T of the blood vessel maps the white blood cell discovered, the number of hubs N, and the time D the red blood cell moves, separated by spaces. (1 ≤ T ≤ 100, 2 ≤ N ≤ 20, 0 ≤ D ≤ 10^9)

After that, T blood vessel maps describing the connections between hubs are given in order from number 1 to number T. The format of each blood vessel map is as follows.

  • The first line contains the number of blood vessels connecting hubs, Mi. (0 ≤ Mi ≤ N^2)
  • The next Mi lines each contain three positive integers a, b, c separated by spaces. This means there are c distinct one-way passages from hub a to hub b. (1 ≤ a, b ≤ N, 1 ≤ c ≤ 1000)
  • No blood vessel map contains a duplicate connection.

When moving from second i to second (i+1), blood vessel map number (i % T + 1) applies. i % T means the remainder when i is divided by T.

Output

The output consists of N lines. The i-th line must contain N integers xi1, xi2, ..., xiN separated by spaces. xij is the number of paths that start at hub i at time 0 and are at hub j exactly at time D, modulo 1,000,000,007.

Examples4

  1. Example 1

    Input
    1 2 4
2
1 1 2
2 2 3
    Expected output
    16 0
0 81

  2. Example 2

    Input
    3 4 5
4
1 2 1
2 3 1
3 4 1
4 1 1
4
1 1 2
2 3 1
3 4 1
4 2 1
5
1 2 1
2 4 1
4 3 1
3 1 1
1 4 1
    Expected output
    0 0 1 0
0 1 0 0
2 0 0 0
4 0 0 2

  3. Example 3

    Input
    1 8 3
12
1 2 1
1 8 1
2 3 1
2 8 1
3 4 1
3 7 1
3 8 1
4 5 1
4 7 1
5 6 1
6 7 1
7 8 1
    Expected output
    0 0 0 1 0 0 1 1
0 0 0 0 1 0 1 1
0 0 0 0 0 1 0 1
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

  4. Example 4

    Input
    1 8 100000000
24
1 2 1
1 8 1
2 1 1
2 3 1
2 8 1
3 2 1
3 4 1
3 7 1
3 8 1
4 3 1
4 5 1
4 7 1
5 4 1
5 6 1
6 5 1
6 7 1
7 3 1
7 4 1
7 6 1
7 8 1
8 1 1
8 2 1
8 3 1
8 7 1
    Expected output
    261245548 769313318 167840464 862450688 445583828 270525651 828293276 976953408
769313318 542054741 65223362 957807341 63263610 545566670 134857214 863984679
167840464 65223362 959076197 916983285 988077461 199284746 461375786 371787307
862450688 957807341 916983285 119640157 267995930 978327505 847171719 483910227
445583828 63263610 988077461 267995930 394594439 718634258 715295769 69712722
270525651 545566670 199284746 978327505 718634258 131562703 197248645 728310434
828293276 134857214 461375786 847171719 715295769 197248645 322189612 142912983
976953408 863984679 371787307 483910227 69712722 728310434 142912983 162707920