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

Нехай $n$ — фіксоване натуральне число. Визначимо незвичне відображення $f$ на множині перестановок перших $n$ натуральних чисел. Розглянемо перестановку x = (x_1, x_2, \ldots, x_n). З неї побудуємо іншу перестановку y = (y_1, y_2, \ldots, y_n) наступним чином: покладемо y_1 = 1. Для кожного i > 1, якщо z = x_{y_{i-1}} не належить до множини Y_{i-1} = \{y_1, \ldots, 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 \leq g(y) \leq R. Оскільки відповідь може бути великою, виведіть її за модулем 10^9+9.