Permutasiyalarda tənliklər

Tutaq ki, $\text{n}$ sabit bir natural ədəddir. Gəlin, bir az fərqli $\text{f}$ əlamətini $n$ ilkin natural ədədlərinin permutasiyaları üzərində təyin edək. Götürək bir permutasiya \textbf{x} = (x_1, x_2, \ldots, x_n). Bu permutasiyadan başqa bir permutasiya \textbf{y} = (y_1, y_2, \ldots, y_n)-ni aşağıdakı şəkildə quracağıq: y_1 = 1 qoyulur. Hər i > 1 üçün, əgər z = x_{y_{i-1}} Y_{i-1} = \{y_1, \ldots, y_{i-1}\} çoxluğunda yoxdursa, y_i = z qoyulur. Əks halda, y_i Y_{i-1} çoxluğunda olmayan ən kiçik natural ədəd olacaq. Permutasiya $y$-ya $x$ permutasiyasının $f$ əlaməti altındakı görüntüsü deyəcəyik, yəni, f(x) = y. Bu qayda ilə əlamətin qurulması tamamlanır.

$g(y)$ funksiyasını f(x)=y tənliyinin həllərinin sayı kimi təyin edək; yəni f(x) = y bərabərliyini ödəyən $x$ permutasiyaların sayı. İndi tapşırıq belədir: verilmiş qeyri-mənfi $L$ və $R$ ədədləri üçün neçə permutasiya $y$ var ki, L \leq g(y) \leq R? Cavabın böyük ola biləcəyini nəzərə alaraq, nəticəni \mathbf{10^9+9}-a görə qalıqla çıxış edin.