Denis je farmár, a každý deň chodí zo svojej farmy do neďalekej dediny. Načo by však išiel po modernej štrkovej ceste, keď si môže spraviť prechádzku lesom. Les pozostáva z $n$ lúk spojených $m$ lesnými cestičkami.
Aby si spestril svoj nudný každodenný život, rád by aby každá jeho prechádzka bola jedinečná — teda aby sa vždy jeho prechádzka líšila aspoň jednou použitou cestičkou od každej predchádzajúcej prechádzky.
Spočítajte, koľko rôznych prechádzok môže Denis podniknúť. Les je orientovaný acyklický graf — teda cestičky idú vždy v smere od farmy do dediny.
V prvom riadku vstupu sú dve celé čísla $2 \leq n \leq 10^5$ a $1 \leq m \leq 3 \cdot 10^5$ — počet lúk a počet cestičiek. Nasleduje $m$ riadkov, každý je popísaný dvomi celými číslami $a, b$ oddelenými jednou medzerou a určuje cestičku z lúky $a$ na lúku $b$. Medzi dvoma lúkami môže viesť viacero chodníčkov — pre potreby tejto úlohy ich považujeme za rôzne. Pre jednoduchosť si Denisovu farmu označíme ako lúku číslo $1$ a dedinu ako lúku číslo $n$.
Vypíšte počet rôznych prechádzok (postupnosť na seba nadväzujúcich cestičiek), ktoré začínajú na farme a končia v dedine. Keďže toto číslo môže byť veľké, vypíšte jeho zvyšok po delení číslom $10^9 + 7$. Dve prechádzky považujeme za rôzne, ak existuje aspoň jedna cestička taká, že je súčasťou jednej prechádzky ale nie tej druhej.
5 9
2 3
1 5
1 2
1 2
2 4
1 3
3 4
4 5
3 5
9