Problem Description
Lele 现在不仅会整数A+B，A*B，还会矩阵A+B，矩阵A*B。
一天，Lele在百无聊赖的时候，突然想起一个很无聊的问题。
对于给定的一个矩阵A，A+A^2+A^3+...+A^K 是多少呢？
其中A^2 表示两个矩阵的乘积A*A，A^3表示三个矩阵的乘积A*A*A，依此类推。
由于这个计算结果太大了，Lele无法把整个结果写出来，但是，他还是想请你告诉他，结果矩阵中到底有多少个非零元素。
Input
本题目包含多组测试，请处理到文件结束。
在每个测试数据的第一行，有三个整数N,M,和K(0<N<1000,0<=M<10*N,N<K<10^100)，其中N代表矩阵A的大小是N*N，K是题目中所描述的K。
接下来有M行，每行有三个整数a,b,c(0<=a,b,<N 且a!=b,0<c<10^9)表示矩阵中第a行第b列的值为c。(矩阵的行数和列数都是从0开始计数)
你可以假定矩阵中主对角线上的数都是1，其余没有提到的元素都是0。
Output
对于每一组测试数据，请在一行里输出结果矩阵里的非0元素的个数。
Sample Input
3 4 4
1 2 1
2 1 1
0 1 1
0 2 1
Sample Output
7
