IOI 2222 即將在粄條巿舉行！粄條市由 $N$ 個區域組成，並且有 $M$ 條高架橋，每條高架橋都是單向的從某一個區域到另一個區域，且有各自所需的通過時間，而且這些高架橋有一個特色，就是無論從任何一個區域 $v$ 開始，都無法經過至少一條高架橋，最後回到區域 $v$。選手們住在區域 $1$，而比賽場地在區域 $N$。

然而由於各種事故，IOI 2222 延期到 12 月舉行，正逢粄條歡樂耶誕城期間，因此主辦單位必須妥善安排交通路線，以避免塞車導致比賽延後。為此，主辦單位會選擇一條從區域 $1$ 到區域 $N$，由若干高架橋組成的需要花費最長時間的路線（粄條市很先進，從一條高架橋抵達一個區域後，總是可以瞬間到達任何一條離開這個區域的高架橋，因此一條路線所需花費的時間就是每條高架橋需要的通過時間總和），主辦單位覺得這樣的路線人潮肯定最少。不過這樣的選擇可能有很多，主辦單位想知道最長的所需花費時間有多長，以及這樣的路線有幾條。

你以為這題會那麼簡單嗎？其實有一群害怕人類科技發展過快的外星人，他們覺得 IOI 2222 的選手都太聰明了，因此希望把他們卡在車陣當中（事實上，IOI 2222 延期到 12 月也是他們的陰謀）。預期到這件事的主辦單位，猜測外星人可能會讓粄條市裡的某一個區域暫時無法通行，主辦單位想知道，對於每個區域 $i$，要是區域 $i$ 無法通行的話，從區域 $1$ 到 $N$ 的最長所需花費時間，以及需要最多時間的路線有幾條。由於數量可能很大，請輸出數量除以 ${10}^9+7$ 的餘數。