eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Рівняння у перестановках

Рівняння у перестановках

Ліміт часу 1 секунда
Ліміт використання пам'яті 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.

Вхідні дані

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

Вихідні дані

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

Приклад

Вхідні дані #1
3 5
0 0
2 2
4 4
0 5
2 1
Вихідні дані #1
4
1
1
6
0