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], ..., x[n]). From this, we will construct another permutation y=(y[1], y[2], ..., 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], ..., 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 ≤ g(y) ≤ R. Since the result can be large, provide the answer modulo 10^9+9.
Input
The first line of the input contains natural numbers n ≤ 10^5 and T ≤ 1000, which represent the length of the permutation and the number of pairs L, R to be processed for the given n. Each of the following T lines contains non-negative integers L, R ≤ 10^18.
Output
For each pair L, R from the input, output on a separate line the remainder when divided by 10^9+9 of the number of permutations y of length n such that L ≤ g(y) ≤ R.