Рівняння у перестановках
Нехай 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, що L ≤ g(y) ≤ R. Так как відповідь може бути великою, то виведіть її по модулю 10^9+9.
Вхідні дані
У першому рядку вхідного файлу задано через пропуск натуральні числа n ≤ 10^5 і T ≤ 1000, довжина перестановки та кількість пар L, R, які необхідно опрацювати для заданого n. У кожному з наступних T рядків задано через пропуск цілі невід'ємні числа L, R ≤ 10^18.
Вихідні дані
Для кожної пари L, R з вхідного файлу виведіть у окремому рядку залишок при діленні на 10^9+9 кількості таких перестановок y довжини n, що L ≤ g(y) ≤ R.