Bicikli

Διοργανώνεται ποδηλατικός αγώνας σε μια χώρα πολύ μακριά. Υπάρχουν ~N~ πόλη στη χώρα, αριθμημένες απο ~1~ εώς ~N~. Υπάρχουν επίσης ~M~ μονόδρομοι μεταξύ των πόλεων. Ο αγώνας θα ξεκινήσει από την πόλη ~1~ και θα τελειώσει στην πόλη ~2~.
Με πόσους διαφορετικούς τρόπους μπορεί να γίνει η διαδρομή; Δύο διαδρομές θεωρούνται διαφορετικές εάν δεν χρησιμοποιούν τους ίδιους ακριβώς δρόμους.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει δύο ακέραιους ~N~ και ~M\;(1 \le N \le 10\,000,\;1 \le M \le 100\,000)~, τον αριθμό των πόλεων και των δρόμων.
Κάθε μία από τις επόμενες γραμμές ~M~ περιέχει δύο διαφορετικούς ακέραιους αριθμούς ~A~ και ~B~, που αντιπροσωπεύουν έναν δρόμο μεταξύ των πόλεων ~A~ και ~B~.
Οι πόλεις μπορούν να συνδέονται με περισσότερους από έναν δρόμους.

Έξοδος

Εκτυπώστε τον αριθμο των διαφορετικών διαδρομών που μπορούν να οριστούν σε μία μόνο γραμμή. Αν αυτός ο αριθμός έχει περισσότερους από εννέα ψηφία, εξάγετε μόνο τα τελευταία εννέα ψηφία του αριθμού. Αν υπάρχουν άπειρες διαδρομές, εκτυπώστε "inf".

Παραδείγματα

input

6 7
1 3
1 4
3 2
4 2
5 6
6 5
3 4

output

3

input

6 8
1 3
1 4
3 2
4 2
5 6
6 5
3 4
4 3

output

inf

input

31 60
1 3
1 3
3 4
3 4
4 5
4 5
5 6
5 6
6 7
6 7
...
...
...
28 29
28 29
29 30
29 30
30 31
30 31
31 2
31 2

output

073741824