Fysty 今天來到了埃歐埃國，埃歐埃國總共有 $n$ 座島嶼，編號分別是 $1$ 到 $n$，其中最著名的兩個島：埃歐島與埃西島的編號分別是 $s$ 和 $t$，這兩個島也是唯二有旅店可以住宿的島嶼。 Fysty 想藉由安排一次跳島旅行來探索偌大的埃歐埃國，這趟旅行會持續 $q$ 天，每天 Fysty 都會從前一天住宿的島嶼前往 $a_j$ 島遊玩，再到另一個島嶼過夜，請注意 Fysty 不喜歡連續兩天住在同一個島嶼，所以他會輪流在埃歐島和埃西島過夜。第一天的時候他會從埃歐島出發。在埃歐埃國上總共有 $m$ 條航線，第 $i$ 條航線在任一時刻都會有一艘小艇從第 $u_i$ 個島嶼出發前往第 $v_i$ 個島嶼，同時也有另一艘小艇從第 $v_i$ 個島嶼出發前往第 $u_i$ 個島嶼，票價皆為 $c_i$ 元。請你幫 Fysty 算出他每天共需要花費至少多少錢在買船票上，並且在花費最少錢的前提下，他安排航線的選擇數對 ${10}^9+7$ 取模的餘數。