Уравнение в перестановках
Пусть 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.