y

y.cpp/in/out

• 时间限制：1.0s
• 空间限制：512MB

题目描述

给定一个无向图，$n$ 个点（从 1 开始编号）、$m$ 条边（长度为 1），每条边有一个权值 $c\ (c \in \{0, 1\})$。

一条路径，可以表示为一个长度为经过边数的 01 串，串的第 $i$ 位为经过的第 $i$ 条边的权值。

两条路径相同，当且仅当表示其的 01 串相同。

求从 1 号点出发、长度为 $d$ 的路径种数。

输入格式

从文件 y.in 中读入数据。

第一行，三个整数，$n, m, d$。

接下来 $m$ 行，每行三个整数 $u, v, c$，代表一条边连接 $u$ 和 $v$，权值为 $c$。

输出格式

输出到文件 y.out 中。

输出一行，一个整数，代表答案。

样例输入

3 2 3
1 2 0
1 3 1

样例输出

4

样例解释

1 -> 2 -> 1 -> 2  =>  000
1 -> 2 -> 1 -> 3  =>  001
1 -> 3 -> 1 -> 2  =>  110
1 -> 3 -> 1 -> 3  =>  111

数据范围

保证 $n \in [1, 90]$，$m \in [0, n(n-1)]$，$d \in [1, 20]$，$u, v \in [1, n]$，$c \in \{0, 1\}$。