AT_pakencamp_2019_day4_e IOI のために

### 题目背景 在 $\text{20XX}$ 年，IOI 已经是家喻户晓的著名比赛，每年夏季和冬季都会举办。 $\text{20XX}$ 年的 IOI 比赛将在 K 国举办，负责人决定扩展广场的道路。 ### 题意 在 IOI 比赛时，可以使用的 K 国土地有 $N$ 块，有 $M$ 条道路穿过。 土地的编号为 $1$ 至 $N$，道路的编号为 $1$ 至 $M$。无论哪两个土地之间，都可以通过道路来往。 道路 $i$ 将土地 $A_i$ 和 $B_i$ 双向连接，夏季通行所需时间为 $S_i$，冬季通行所需时间为 $W_i$。 从土地 $1$ 到达土地 $N$ 的路线称为**远足路线**。求在夏天和冬天中至少一个季节里，有几条满足 **** 的远足路线。 答案对 $10^9+7$ 取余。

第一行读入两个整数 $N$ 和 $M$。 接下来 $M$ 行，每行读入四个整数 $A_M,B_M,S_M,W_M$。

输出一行一个整数，表示在夏天或冬天的至少一个季节中，满足如上条件的远足路线的个数，并对 $10^9+7$ 取余。

**本题使用捆绑测试。** - Subtask 1(5 pts) : 满足 $M=N-1$。 - Subtask 2(15 pts) : 满足 $N\le 10$。 - Subtask 3(20 pts) : 对于任意的 $ 1\ \leq\ i\ \leq\ M $，满足 $ S_i\ =\ W_i $。 - Subtask 4(35 pts) : 满足 $N\le1000$。 - Subtask 5(25 pts) : 无附加条件。 对于 $100\%$ 的数据，保证 - 输入均为整数 - $ 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) $ - $ 1\ \leq\ S_i,\ W_i\ \leq\ 10^9\ (1\ \leq\ i\ \leq\ M) $ - 每两块土地之间都可以通过道路相来往 ### 样例 1 解释 满足条件的远足路线有以下 $ 6 $ 条。 - 按照道路 $ 1,\ 7 $ 的顺序通过，在夏天和冬天都满足条件； - 按照道路 $ 2,\ 5,\ 7 $ 的顺序通过，在夏天和冬天都满足条件； - 按照道路 $ 2,\ 6,\ 7 $ 的顺序通过，在冬天满足条件； - 按照道路 $ 3,\ 5,\ 7 $ 的顺序通过，在冬天满足条件； - 按照道路 $ 3,\ 6,\ 7 $ 的顺序通过，在冬天满足条件； - 按照道路 $ 2,\ 8 $ 的顺序通过，在夏天满足条件。 [@lihl](https://www.luogu.com.cn/user/711887) 提供翻译。