410084: GYM103940 A Advanced Player Setup

Ivanovich is obsessed with a new game, Algorithmic Creed, here you work with your creed trying to give free will to the coders of the world, meanwhile in the other side the managers, also known as "templars" want to take away coders free will and deprive them of their human nature.

An important part of this game is to obtain and update items to be a stronger coder, like a gaming mouse, a new keyboard, a better monitor... because you know that the most important part of coding is the setup.

The game has $$$N$$$ items numbered from $$$1$$$ to $$$N$$$ and the only way to obtain new items is performing a trade. The only item you can buy directly is a pen (for writing pseudocode in paper) which is always represented with the number $$$1$$$, you can always buy it for 1 coin and you can buy it several times. In this game you have the ability to trade items for another one which is always better, the game has a list of item trading rules, each rule describe the item $$$u$$$ as a requirement to obtain item $$$v$$$ and the number of $$$c$$$ coins you have to give to perform the trade. In order to obtain item $$$v$$$ you need to trade all items $$$u$$$ that are a requirement for $$$v$$$ and pay the number of coins associated to trade $$$u$$$ for $$$v$$$, after the trade you will lose the $$$u$$$ items, and the coins, but obtain item $$$v$$$.

Ivanovich has never been good at games, since he always loses focus and begins to think about programming problems. He is wondering how many different setups he can build in the game if he has $$$C$$$ coins to trade. Can you help Ivanovich to solve this weird problem so he can go back to the game?

A setup is different from another one if there is at least one different item. A setup must have at least one item.

The first line of input contains three integers separated by a space $$$N$$$ $$$(1 \leq N \leq 10^5)$$$, $$$M$$$ $$$(1 \leq M \leq 10^5)$$$, $$$C$$$ $$$(1 \leq C \leq 10^2)$$$, representing the number of items in the game, the number of trading rules available and the number of coins available respectively.

Each of the next $$$M$$$ lines contains three integers separated by a space, $$$u_i$$$ $$$(1 \leq u_i \leq N)$$$, $$$v_i$$$ $$$(1 \leq v_i \leq N)$$$, $$$c_i$$$ $$$(1 \leq c_i \leq C)$$$, indicating that in the $$$i$$$-th trading rule the item $$$u_i$$$ is a requirement for $$$v_i$$$ paying $$$c_i$$$ coins.

In the first and only line, print the number of different setups Ivanovich can build. As the answer might be very large, please output the answer modulo $$$10^9 + 7$$$.

3 2 4
1 2 1
2 3 1

10

3 3 4
1 2 1
1 3 1
2 3 1

8