Given an undirected, weighted graph of n vertices and m edges. Find the number of shortest paths from 1 to n.
### Input
- The first line contains 2 integers n,m.
- The next m lines, each line contains 3 integers u,v,w, there is an edge of weight w connecting u,v .
### Output
- Print the number of shortest paths from 1 to n, modulo 109+7.
### Constraints
- 1≤n,m≤2×105.
- 1≤u,v≤n.
- 1≤w≤109.
### Example
Input:
33121232133
Output:
2