eolymp
bolt
Try our new interface for solving problems
Problems

Уравнение в перестановках

Уравнение в перестановках

Time limit 1 second
Memory limit 256 MiB

Пусть n - фиксированное натуральное число. Давайте построим довольно необычное отображение f на множестве перестановок первых n натуральных чисел. Пусть x=(x[1], x[2], ..., x[n]) - некоторая перестановка. Построим по ней перестановку y=(y[1], y[2], ..., y[n]) следующим образом. Пусть y[1]=1, а при i>1 если z=x[y[i-1]] не принадлежит множеству Y_{i-1}={y[1], ..., y[i-1]}, то y[i]=z, иначе y[i] равно наименьшему натуральному числу, которое не принадлежит Y_{i-1}. Будем называть перестановку y образом перестановки x при отображении f, то есть f(x)=y. Итак, отображение построение.

Обозначим через g(y) количество решений уравнения f(x)=y, то есть количество тех перестановок x, для которых f(x)=y. Теперь задача. Для заданных целых неотрицательных чисел L и R требуется найти количество таких перестановок y, что Lg(y)R. Так как ответ может быть большим, то выведите его по модулю 10^9+9.

Input data

В первой строке входного файла заданы через пробел натуральные числа n10^5 и T1000, длина перестановки и количество пар L, R, которые необходимо обработать для данного n. В каждой из последующих T строк заданы через пробел целые неотрицательные числа L, R10^18.

Output data

Для каждой пары L, R из входного файла выведите в отдельной строке остаток при делении на 10^9+9 количества таких перестановок y длины n, что Lg(y)R.

Examples

Input example #1
3 5
0 0
2 2
4 4
0 5
2 1
Output example #1
4
1
1
6
0