Problem Description

It is the year 20XX. The IOI (International Olympiad in Iconoclasm) has become a famous competition known to everyone, held every summer and winter.

The IOI in 20XX will be held in the Kingdom of Kclc. Suqare, who manages the IOI Kingdom Committee, has decided to consider the route for the excursion.

There are $ N $ lands in the Kingdom of Kclc that can be used for the IOI, and there are $ M $ roads connecting these lands. The lands are numbered from $ 1 $ to $ N $, and the roads are numbered from $ 1 $ to $ M $. Any two lands can be reached from one another by traveling through some roads.

Road $ i $ connects land $ A_i $ and land $ B_i $ bidirectionally, and the travel time is $ S_i $ in summer and $ W_i $ in winter.

A route starting from land $ 1 $ and arriving at land $ N $ is called a hiking route.

How many hiking routes satisfy the following condition in at least one of the seasons, summer or winter?

• There is no hiking route with a shorter total travel time.

Since the answer can be very large, output the remainder when divided by $ 10^9+7 $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ A_1 $ $ B_1 $ $ S_1 $ $ W_1 $ : $ A_M $ $ B_M $ $ S_M $ $ W_M $

Output Format

Output the number of hiking routes that satisfy the condition in at least one of the seasons, summer or winter, modulo $ 10^9+7 $.

Sample Input and Output

Sample Input #1

4 8
1 2 3 2
1 3 2 1
1 3 3 1
2 2 1 1
2 3 1 1
2 3 2 1
2 4 1 2
3 4 2 4

Sample Output #1

6

Sample Input #2

4 5
1 2 3 6
2 3 1 2
3 4 2 5
1 3 5 3
2 4 4 2

Sample Output #2

2

Sample Input #3

20 77
9 16 65551022 36847141
4 8 169905126 234841269
8 18 61782163 101070315
8 9 763292109 656192270
1 18 76893781 240632078
3 19 601597138 476288881
5 19 595403102 581080612
3 6 980642190 183697163
6 9 663706146 95151932
11 18 679581087 523262198
12 16 293035618 152800086
3 7 814717585 273291118
1 2 853500661 870996856
2 3 526446904 394372085
2 9 75096934 115522990
4 9 599545324 421351001
1 13 282807719 968765138
6 15 458441410 364130005
1 4 178858403 334122865
4 4 242708006 509603317
8 13 368467895 338762793
13 17 697663167 640858525
11 20 238453071 271106570
2 17 126970225 114980011
14 18 279244522 277866206
11 20 238453071 271106570
5 20 714162258 622887639
4 12 694170286 610998228
9 16 65551022 36847141
15 15 341887831 393369008
3 8 311942139 377343175
1 8 15111618 99281596
2 4 674642258 536873991
2 16 9545912 78675849
1 8 15111618 99281596
12 20 121899250 49599586
14 20 638789636 516502562
5 17 699705205 614143827
7 13 480049964 311871500
9 14 422265424 394103067
7 10 230695689 160298785
2 20 141427278 488804437
9 16 65551022 36847141
2 4 746378429 794786225
1 13 684196511 438044389
9 19 97765056 384638724
8 14 599920464 622509237
16 20 446862361 693104823
2 20 141427278 250722614
17 18 964998636 785624956
11 20 238453071 271106570
1 3 327053757 476624771
1 5 327955959 908911545
3 11 429421111 769824924
7 19 113311100 202997763
13 18 205913938 237692478
1 17 980470886 985976867
3 12 545974932 468496322
6 19 312631863 292591718
11 15 651379358 427422180
3 8 311942139 377343175
8 17 965359268 886695271
3 20 667874182 518095908
12 17 107442197 40855774
2 10 321338667 306331990
4 13 103949316 103921524
9 10 246241733 165856762
7 14 406719380 271697772
7 8 747746065 755010172
1 9 778403727 755473866
8 17 965359268 886695271
5 11 475709187 351781069
8 11 751809642 869885243
5 19 595403102 581080612
19 20 118759156 41807027
3 19 646592547 476288881
3 12 850613737 468496322

Sample Output #3

190

Notes/Hints

Constraints

• All inputs are integers.
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq N \ (1 \leq i \leq M)$
• Any two lands can be reached from one another by traveling through some roads.
• $1 \leq S_i, W_i \leq 10^9 \ (1 \leq i \leq M)$

Partial Points

This problem is divided into several sub-tasks, and you will be considered to have solved a sub-task if you correctly answer all test cases for that sub-task.

The score for your submission will be the sum of the points for the sub-tasks you have solved.

1. (5 points) $ M = N - 1 $
2. (15 points) $N \leq 10$
3. (20 points) For any $1 \leq i \leq M$, $ S_i = W_i $
4. (35 points) $N \leq 1000$
5. (25 points) No additional constraints.

Sample Explanation 1

The following 6 hiking routes satisfy the condition:

• Travel through road $ 1 $, then road $ 7 $. Satisfies the condition in both summer and winter.
• Travel through road $ 2 $, then road $ 5 $, then road $ 7 $. Satisfies the condition in both summer and winter.
• Travel through road $ 2 $, then road $ 6 $, then road $ 7 $. Satisfies the condition only in winter.
• Travel through road $ 3 $, then road $ 5 $, then road $ 7 $. Satisfies the condition only in winter.
• Travel through road $ 3 $, then road $ 6 $, then road $ 7 $. Satisfies the condition only in winter.
• Travel through road $ 2 $, then road $ 8 $. Satisfies the condition only in summer.

见题面 Input 部分

见题面 Output 部分