E - IOI のために Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

時は 20XX 年．IOI (International Olympiad in Iconoclasm) はいまや誰もが知る有名な大会となり，毎年の夏と冬に開催されています．

20XX 年の IOI は Kclc 王国で開かれます．IOI 王国委員会の管理人を務めるスクエアは，エクスカージョンの道のりを考えることにしました．

IOI で使用できる Kclc 王国の土地は N 個あり，この間には M 本の道路が通っています．土地には 1 から N の，道路には 1 から M の番号がつけられています．どの 2 土地の間も，道路をいくつか通って行き来できます．

道路 i は土地 A_i と 土地 B_i を双方向につないでおり，通行にかかる時間は夏のとき S_i，冬のとき W_i です．

土地 1 から出発し土地 N に到着する道のりを 遠足ルート と呼ぶことにします．

夏か冬の少なくとも片方の季節に次の条件を満たすような遠足ルートは何通りあるでしょうか．

  • 通行にかかる総時間がより短いような遠足ルートが存在しない．

答えは非常に大きくなることがあるので，10^9+7 で割ったあまりを出力してください．

制約

  • 入力はすべて整数
  • 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)
  • どの 2 土地の間も，道路をいくつか通って行き来できる
  • 1 \leq S_i, W_i \leq 10^9\ (1 \leq i \leq M)

部分点

この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．

提出したソースコードの得点は，正解した小課題の点数の合計となります．

  1. (5 点) M=N-1 を満たす．
  2. (15 点) N \leq 10 を満たす．
  3. (20 点) 任意の 1 \leq i \leq M について，S_i = W_i を満たす．
  4. (35 点) N \leq 1000 を満たす．
  5. (25 点) 追加の制約はない．

入力

入力は以下の形式で標準入力から与えられます．

N M
A_1 B_1 S_1 W_1
:
A_M B_M S_M W_M

出力

夏か冬の少なくとも片方の季節に条件を満たすような遠足ルートの個数を 10^9+7 で割ったあまりを出力してください．

入力例 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

出力例 1

6

条件を満たす遠足ルートは以下の 6 つです．

  • 道路 1, 7 の順に通る．夏と冬の両方で条件を満たす．
  • 道路 2, 5, 7 の順に通る．夏と冬の両方で条件を満たす．
  • 道路 2, 6, 7 の順に通る．冬のときのみ条件を満たす．
  • 道路 3, 5, 7 の順に通る．冬のときのみ条件を満たす．
  • 道路 3, 6, 7 の順に通る．冬のときのみ条件を満たす．
  • 道路 2, 8 の順に通る．夏のときのみ条件を満たす．

入力例 2

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

出力例 2

2

入力例 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

出力例 3

190