Equations in Permutations

Let $n$ be a fixed natural number. We will define an unusual mapping $f$ on the set of permutations of the first $n$ natural numbers. Consider a permutation x = (x_1, x_2, \ldots, x_n). From this, we will construct another permutation y = (y_1, y_2, \ldots, y_n) as follows: set y_1 = 1. For each i > 1, if z = x_{y_{i-1}} is not in the set Y_{i-1} = \{y_1, \ldots, y_{i-1}\}, then let y_i = z. Otherwise, y_i will be the smallest natural number not in Y_{i-1}. We call the permutation $y$ the image of permutation $x$ under the mapping $f$, i.e., f(x) = y. This completes the construction of the mapping.

Let $g(y)$ represent the number of solutions to the equation f(x) = y, which is the count of permutations $x$ for which f(x) = y. Now, for the task: given non-negative integers $L$ and $R$, determine the number of permutations $y$ such that L \leq g(y) \leq R. Since the result can be large, provide the answer modulo 10^9+9.