Task DescriptionDiscussion (0)

From the first line of the standard input read three integers

To the standard, in

Task :: 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**INPUT:**

From 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**.

**OUTPUT:**

To 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:

Output:

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...)

**3 3 20000**

1 2

2 3

3 1

1 2

2 3

3 1

Output:

**0**

0

1

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:

Output:

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.

**2 3 3**

1 1

1 2

1 1

1 1

1 2

1 1

Output:

**8**

4

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

Available Languages

Task info

Name: | z-mario |

Time: | 0.5 sec. |

Memory: | 16 MB |

#Tests: | 20 |

AddedBy: | admin |

Task Ratings

Difficulty: | 3.8 (12 votes) |

Quality: | 4.8 (11 votes) |

Acceptance Rate

Recent Submissions

Fastest Solutions

User | Time |
---|---|

1010011010 | 0.265 s. |

senator | 0.28 s. |

superzz | 0.302 s. |

ivan100sic | 0.35 s. |

mfolnovic | 0.359 s. |

rusinsr | 0.363 s. |

mmilisic | 0.368 s. |

RobertGerbicz | 0.371 s. |

matteo123 | 0.371 s. |

_qwAker_ | 0.373 s. |

Solved By