Permutations of Project

Consider the alphabet A made out of the letters of the word "project": A={c,e,j,o,p,r,t}. Let T(n) be the number of strings of length n consisting of letters from A that do not have a substring that is one of the 5040 permutations of "project".

Find T(10¹²). Give the last 9 digits of your answer.

Written by gamwe6 who lives and works in San Francisco building useful things. You should follow him on Twitter