Рассмотрим алфавит A, состоящий из букв слова "project": A={c,e,j,o,p,r,t}.
Пусть T(n) будет количеством строк длиной n, состоящих из букв алфавита A и не содержащих в себе ни одной подстроки, являющейся одной из 5040 перестановок слова "project".

Найдите T(10¹²). В качестве ответа приведите последние 9 цифр полученного числа.