Busy Beaver 有一棵拥有 $N$ 个结点的非常大的树，其中对于某个整数 $k \ge 1$，有 $N = 2^k - 1$。他希望切断其中的一些边，使得得到的森林恰好有 $k$ 个连通分量，其顶点数分别为 $1, 2, 4, 8, \dots, 2^{k-1}$，且每个连通分量都构成一条简单路径。请帮助 Busy Beaver 计算满足该条件的切边方案数，模 $10^9 + 7$ 的结果。

为了减小输入文件的大小，树以压缩格式给出。树中包含 $M$ 个标记为 $1, \dots, M$ 的关键结点，它们由 $M - 1$ 条路径连接。第 $i$ 条路径连接关键结点 $u_i$ 和 $v_i$，且由 $\ell_i$ 条边组成，其中 $1 + \sum_{i=1}^{M-1} \ell_i = N$。

输入格式

第一行包含两个整数 $N$ 和 $M$（$1 \le N \le 2^{60} - 1$，$1 \le M \le \min(N, 10^5)$，且对于某个整数 $k \ge 1$ 有 $N = 2^k - 1$）。

接下来的 $M - 1$ 行，每行包含三个整数 $u_i$、$v_i$ 和 $\ell_i$（$1 \le u_i, v_i \le M$，$u_i \ne v_i$，$1 \le \ell_i \le N - 1$），表示 $u_i$ 和 $v_i$ 之间一条长度为 $\ell_i$ 的路径。

树中的总顶点数等于 $N$（即 $1 + \sum_{i=1}^{M-1} \ell_i = N$）。

输出格式

输出一个整数：满足条件的划分方案数模 $10^9 + 7$ 的结果。

子任务

本题共有三个子任务。

• （10 分）：$N \le 2^9 - 1$。
• （30 分）：$N \le 2^{17} - 1$。
• （60 分）：无附加限制。

样例

输入样例 1

7 4
1 2 1
1 3 2
1 4 3

输出样例 1

5

输入样例 2

1 1

输出样例 2

1

说明

在第一个样例中，将树划分的 5 种方式如下所示：