AT_pakencamp_2019_day4_e IOI のために

[problemUrl]: https://atcoder.jp/contests/pakencamp-2019-day4/tasks/pakencamp_2019_day4_e 時は 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 $ で割ったあまりを出力してください．

入力は以下の形式で標準入力から与えられます． > $ N $ $ M $ $ A_1 $ $ B_1 $ $ S_1 $ $ W_1 $ : $ A_M $ $ B_M $ $ S_M $ $ W_M $

夏か冬の少なくとも片方の季節に条件を満たすような遠足ルートの個数を $ 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 点) 追加の制約はない． ### Sample Explanation 1 条件を満たす遠足ルートは以下の $ 6 $ つです． - 道路 $ 1,\ 7 $ の順に通る．夏と冬の両方で条件を満たす． - 道路 $ 2,\ 5,\ 7 $ の順に通る．夏と冬の両方で条件を満たす． - 道路 $ 2,\ 6,\ 7 $ の順に通る．冬のときのみ条件を満たす． - 道路 $ 3,\ 5,\ 7 $ の順に通る．冬のときのみ条件を満たす． - 道路 $ 3,\ 6,\ 7 $ の順に通る．冬のときのみ条件を満たす． - 道路 $ 2,\ 8 $ の順に通る．夏のときのみ条件を満たす．