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$$$.
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 a single integer: the number of such partitions modulo $$$10^9 + 7$$$.
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.
7 41 2 11 3 21 4 3
5
1 1
1
In the first sample test case, the $$$5$$$ ways to partition the tree are as follows:
