C. Tree Partition
time limit per test
7 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Busy Beaver has a very large tree with $$$N$$$ vertices, where $$$N = 2^k - 1$$$ for some integer $$$k \ge 1$$$. He wants to cut some of its edges such that the resulting forest has exactly $$$k$$$ connected components with $$$1, 2, 4, 8, \dots, 2^{k-1}$$$ vertices, respectively, and each component forms a simple path. Help Busy Beaver count the number of ways to cut edges to satisfy this condition, modulo $$$10^9 + 7$$$.

To reduce the size of the input, the tree is given in a compressed format. There are $$$M$$$ key vertices labelled $$$1,\dots,M$$$, connected by $$$M-1$$$ paths. The $$$i$$$-th path connects key vertices $$$u_i$$$ and $$$v_i$$$ and consists of $$$\ell_i$$$ edges, where $$$1+\sum_{i=1}^{M-1} \ell_i = N$$$.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N \le 2^{60}-1$$$, $$$1 \le M \le \min(N,10^5)$$$, $$$N = 2^k - 1$$$ for some integer $$$k \ge 1$$$).

Each of the next $$$M-1$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$\ell_i$$$ ($$$1 \le u_i,v_i \le M$$$, $$$u_i \ne v_i$$$, $$$1 \le \ell_i \le N-1$$$), specifying a path between $$$u_i$$$ and $$$v_i$$$ of length $$$\ell_i$$$.

The total number of vertices in the tree is equal to $$$N$$$ (formally, $$$1+\sum_{i=1}^{M-1} \ell_i = N$$$).

Output

Output a single integer: the number of such partitions modulo $$$10^9 + 7$$$.

Scoring

There are three subtasks for this problem.

  • ($$$10$$$ points): $$$N \le 2^9-1$$$.
  • ($$$30$$$ points): $$$N \le 2^{17}-1$$$.
  • ($$$60$$$ points): No additional constraints.
Examples
Input
7 4
1 2 1
1 3 2
1 4 3
Output
5
Input
1 1
Output
1
Note

In the first sample test case, the $$$5$$$ ways to partition the tree are as follows: