Permutasiyaların dərəcələri

Qoy $N$ təbii ədəd olsun və S = \{ 1, 2, 3, \ldots, N \} çoxluğunu təşkil etsin. f : S \to S funksiyası gözəl adlanır, əgər elə bir bijektiv g : S \to S funksiyası varsa ki, $S$ çoxluğundakı istənilən $x$ üçün g(g(g(\ldots g(x) \ldots ))) = f(x) bərabərliyi təmin olunur, burada $g$ dəqiq $d$ dəfə tətbiq edilir.

Gözəl funksiyaların sayını tapmaq lazımdır. Cavab çox böyük ola biləcəyi üçün onu $1000000009$ modulu ilə çıxış etmək tələb olunur.