注意

yukicoder contest 279 (Zelkova and Cherry) の問題は 難易度順に並んではいない. よって, 問題文や難易度を表すの星の数, 正解者数等といった公開されている情報から問題を取捨選択することを強く推奨する.

問題文

$0$ から $N$ の番号がついた $N+1$ 個の頂点といくつかの有向辺からなる有向グラフがある. このグラフには $j=1, \dots, M $ に対して, 頂点 $u_j$ から 頂点 $v_j$ へ長さ $l_j$ で結ぶ有向辺が $a_j$ 本ある. なお, この有向グラフに自己ループは存在しない. このグラフにおいて, 頂点 $0$ から頂点 $N$ への歩道を全て考えたとき, 長さの総和が有限ならば, 総和を $10^9+7$ で割った余りを求め, 無限ならば, その旨を報告せよ. なお, 2つの歩道について, 辿った頂点の順番が同じでも, 用いた辺が同じでなければ, 異なる歩道とする.

訳注

有向辺 $e$ について, $s(e), t(e)$ でそれぞれ $e$ の始点, 終点を表すとする. このとき, 有向辺 $e$ に対して, $s(e)=t(e)$ であるとき, 辺 $e$ は自己ループであるという.

辺の列 $e_1, \dots, e_k$ が以下をみたすとき, $W=(e_1, \dots, e_k)$ は歩道であるという.

• $i=1, \dots, k-1$ に対して, $t(e_i)=s(e_{i+1})$ を満たす.

歩道 $W=(e_1, \dots, e_k)$ に対して, 辺 $e$ の長さを $l(e)$ としたとき, 歩道 $W$ の長さ $l(W)$ を, $l(W)=\sum_{i=1}^k l(e_i)$ とする.

制約

• $1 \leq N \leq 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $0 \leq u_j, v_j \leq N$
• $u_j \neq v_j$
• $1 \leq l_j \leq 10^9$
• $1 \leq a_j \leq 10^9$
• 入力は全て整数である.

入力

$N\ M$
$u_1\ v_1\ l_1\ a_1$
$\vdots$
$u_M\ v_M\ l_M\ a_M$

出力

頂点 $0$ から頂点 $N$ への歩道の長さの総和が有限ならば, その総和を $10^9+7$ で割った余りを出力せよ. もし, 無限ならば, INF と出力せよ. どちらにせよ, 最後に改行を忘れないこと.

サンプル

3 4
0 1 2 1
1 2 1 1
2 3 3 1
0 3 4 1

10

3 4
0 1 1 1
1 2 1 1
2 1 1 1
2 3 1 1

INF

1 2
0 1 3 2
0 1 4 3

18