Codah ClubTrain. Submit. Improve.
Sign in
English
#000137

z-mario

Little Z. has found his old GameBoy. One of his favorite games used to be Super Zario. The game is based on the Super Mario game, but has some different rules. You are starting from Level 1, each level is shown on the map. After completing that level, you have a choice to go to different levels. For example, after completing Level 1, you can play Level 1 again, or Level 2, or Level 5, etc.., that means that on the map of the levels there is an one way path between level 1 and: level1, level2, level5, etc..


Mister Little Z always completes the level, he is so good at the game that he never dies. So he came up with the following questions. "In how many ways you can end-up at each of the levels, if you have successfully completed exactly K levels". Assuming you are starting from Level 1


InputFrom the first line of the standard input read three integers N, M, K. Where (1 <= N <= 100) is the number of levels, (1 <= M <= 100000) is the number of one way roads that connect the levels, and ( 1 <= K <= 2000000000) is the number of levels you should complete. From each of the next M lines read two integers A and B, where (1 <= A,B <= N) representing a road from level A to level B.

OutputTo the standard, in N lines write N integer, representing the number of ways you can end-up at the corresponding level, after completing exactly K levels. Output the number of ways modulo 4096

Input:
3 3 20000
1 2
2 3
3 1
Output:
0
0
1
Explanation: After completing each level you can only take one path, therefore, after completing 20000 levels you must end-up at level 3 (i.e. you are completing levels: 1, 2, 3, 1, 2, 3, 1, 2, 3...)

Input:
2 3 3
1 1
1 2
1 1
Output:
8
4
Explanation: In this case we have to ways of going from level 1 back to level 1. So in three steps we can end up in level one in 2*2*2 ways. In order to end-up in level 2 we have to have the last step being going from level 1 to level 2, so we can go from level 1 to level 1 in 2*2 ways (in 2 steps), and then take the final step to level 2.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.