Twelve faces of different colors

Let there be N distinct colors. Let a_n = (a_n-1 + a_n-2) % 9 with a₁ = a₂ = 1 Consider the ways to paint all the faces of dodecahedron using these N distinct colors. If selected, you can use up to a_i+2 but no less than 2 of i_th color where i = 1 to N. What is the total number of ways to paint a dodecahedron if N = 1000? Answer format: number Example: 652706 if N = 5 or 130992447 if N = 10 [My timing: 2s]