[SXZOI 2024 E] 哮

题目背景

是什么在黑夜嚎叫？

题目描述

有一个 $n$ 个点，$m$ 条边的有向无环图。每条边上有边权。

定义一条路径的权值为路径上所有边权的异或值。现在对于所有从节点 $1$ 出发走到节点 $n$ 的路径，输出这些路径的权值和。答案对 $998244353$ 取模。

输入格式

第一行两个正整数 $n, m$。

接下来 $m$ 行。每行三个正整数 $u_i, v_i, w_i$ 表示一条从 $u_i$ 到 $v_i$ 的有向边，边权为 $w_i$。

输出格式

一行一个非负整数，表示答案。

样例 #1

样例输入 #1

3 4
1 2 114
1 2 514
2 3 1919
2 3 810

样例输出 #1

4362

样例 #2

样例输入 #2

2 1
1 2 1073741823

样例输出 #2

75497470

提示

对于所有数据，保证 $1 \leq n, m \leq 2 \times 10^5, 1 \leq u_i < v_i \leq n, 0 \leq w_i < 2^{30}$。

对于 $40%$ 的数据，保证 $0 \leq w_i < 64$。