В городе есть сеть метро, состоящая из n станций, пронумерованных от 1 до n, и m двусторонних перегонов между ними.

Поездка по каждому перегону занимает ровно одну единицу времени. Требуется определить:

• минимальную длину маршрута от станции 1 до станции n;
• количество различных маршрутов такой минимальной длины.

Два маршрута считаются различными, если они отличаются хотя бы одной станцией или хотя бы одним перегоном.

Так как число кратчайших маршрутов может быть очень большим, выведите его по модулю 1000000007.

Если добраться от станции 1 до станции n невозможно, выведите -1 0.

Входные данные

В первой строке даны два целых числа n и m — количество станций метро и количество перегонов.

В следующих m строках записаны по два целых числа u и v — номера станций, соединённых двусторонним перегоном.

Выходные данные

Выведите два целых числа:

• длину кратчайшего маршрута от станции 1 до станции n;
• количество кратчайших маршрутов по модулю 1000000007.

Если маршрута не существует, выведите -1 0.

Ограничения

• 1 <= n <= 200000
• 0 <= m <= 300000
• 1 <= u, v <= n
• Перегоны соединяют различные станции
• Между одной и той же парой станций может быть несколько перегонов

Примеры

Пример 1

Входные данные

1 0

Выходные данные

0 1

Пример 2

Входные данные

2 1
1 2

Выходные данные

1 1