问题背景

$\dfrac 1 4$ 遇到了一道水题，叕完全不会做，于是去请教小 D。小 D 懒得理 $\dfrac 1 4$，直接就离开了。于是，$\dfrac 1 4$ 只好来问你，

这道题是这样的：

问题描述

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

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

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

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

输入格式

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

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

输出格式

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

样例

Input

3 2 3
1 2 0
1 3 1

Output

4

Explanation

$$ 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \Rightarrow 000, 1 \rightarrow 2 \rightarrow 1 \rightarrow 3 \Rightarrow 001, 1 \rightarrow 3 \rightarrow 1 \rightarrow 2 \Rightarrow 110, 1 \rightarrow 3 \rightarrow 1 \rightarrow 3 \Rightarrow 111 $$

子任务

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

时限 1s，空限 512M

来源

2018 国庆雅礼 NOIP 培训。一切权利归原作者所有。侵权删除。