题目描述

NN也是要回家过年的呢。

NN所在的国家有 n 座城市，m 条有向道路，第 i 条道路由城市$u_i$通往城市$v_i$，通行费为 $w_i$。

作为一头豪气的N，希望他回家的花费是一个特殊的数字(例如666元)。具体的说，NN希望从城市1移动到城市n，并恰好花费a元。

请你告诉NN，他有多少种回家的方案?

输入描述

第一行三个整数$n,m,a(1≤n≤100,1≤m≤1000,1≤a≤1000)$，含义如题面所示。 接下来$m$行，第$i$行三个整数 $u_i,v_i, w_i(1 ≤ u_i,v_i \le n,1≤ w_i ≤ a)$，描述了一条道路。

输出描述

如果NN回家的方家数大于等于 20220201种，请你在第一行输出All roads lead to Home!，然后在第二行输出回家的方案数对 20220201 取模的结里

否则只需要输出一行一个整数，表示NN回家的方案数。

样例

输入

3 6 2
1 2 1
1 2 1
1 2 1
2 3 1
2 3 1
2 3 1

输出

9

说明

从城市一到城市二有3种不同的走法，从城市二到城市三也有3种不同的走法，根据乘法原理我们可以知道，一共有3x3=9种不同的回家方法。