如果海棠称一个图是完美的，当且仅当对于任意一对顶点 $(x, y)$ 和所有 $z \in [0, 2^w)$，都存在一条从 $x$ 到 $y$ 的路径（不一定是简单路径），使得路径上所有边的权值异或和等于 $z$。特别地，如果一条边被经过多次，其权值在异或和中会被计算多次。

简单图是指不包含重边或自环的图。

如果存在一对顶点 $(u, v)$，使得一个图包含边 $(u, v)$ 而另一个图不包含，或者边 $(u, v)$ 的权值在两个图中不同，则认为这两个图是不同的。

给定四个整数 $n, m, m_0, w$，求满足以下条件的完美简单无向图的数量：具有 $n$ 个顶点，$m$ 条边，边权在 $[0, 2^w)$ 范围内，且包含给定的 $m_0$ 条边。

输出答案对 998244353 取模的结果。

输入格式

第一行包含四个整数 $n, m, m_0, w$ ($1 \le n \le 32, n - 1 \le m \le \frac{n(n-1)}{2}, 0 \le m_0 \le m, 0 \le w \le 60$)。

接下来 $m_0$ 行，每行包含三个整数 $u_i, v_i, c_i$ ($1 \le u_i, v_i \le n, 0 \le c_i < 2^w$)，表示一条边。

保证给定的边构成一个简单图。

输出格式

仅一行，包含一个整数——答案对 998244353 取模的结果。

样例

输入 1

3 3 1 1
1 2 1

输出 1

2

输入 2

4 6 0 3

输出 2

86016

输入 3

11 45 14 19
1 2 123
2 3 456
3 4 789
4 5 890
6 7 233
7 8 2333
8 9 23333
9 10 233333
6 8 333333
7 9 433333
8 10 0
11 1 4307
11 2 5307
11 3 6418

输出 3

783514377