My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too. Or just jump to my GitHub repository.

       
#include <iostream>
       
#include <array>
       
 
       
// "project" has 7 distinct letters

       
const auto WordSize = 7;
       
enum Letters { P = 0, R = 1, O = 2, J = 3, E = 4, C = 5, T = 6 };
       
 
       
// only the last nine digits

       
const unsigned int Modulo = 1000000000;
       
 
       
// ---------- first algorithm ----------

       
 
       
// super-slow brute-force algorithm, becomes unusable for numLetters > 10

       
unsigned long long bruteForce(unsigned int numLetters)
       
{
       
  // bruteForce( 7) =    818503
       
  // bruteForce( 8) =   5699280
       
  // bruteForce( 9) =  39688327
       
  // bruteForce(10) = 276386929
       
  unsigned long long result = 0;
       
 
       
  // 7^numLetters
       
  unsigned long long maxId = 1;
       
  for (unsigned long long exponent = 1; exponent <= numLetters; exponent++)
       
    maxId *= WordSize;
       
 
       
  // iterate over all 7^numLetters combinations
       
  for (unsigned long long i = 0; i < maxId; i++)
       
  {
       
    // convert the current number to letters (it's like converting from decimal to base 7)
       
    auto id = i;
       
    Letters letters[20];
       
    for (unsigned int letter = 0; letter < numLetters; letter++)
       
    {
       
      // I use the data type "Letters" to simplify debugging
       
      letters[letter] = (Letters)(id % WordSize);
       
      id /= WordSize;
       
    }
       
 
       
    // look at each group of 7 consecutive letters
       
    bool isProject = false;
       
    for (unsigned int from = 0; from + WordSize <= numLetters; from++)
       
    {
       
      // build a bitmask:
       
      unsigned int mask = 0;
       
      for (unsigned int current = 0; current < WordSize; current++)
       
        mask |= 1 << letters[from + current];
       
 
       
      // all seven letters used ?
       
      if (mask == 127) // 2^7 - 1 = 127
       
      {
       
        isProject = true;
       
        break;
       
      }
       
    }
       
 
       
    // no seven consecutive letters can be re-order to the word "PROJECT"
       
    if (!isProject)
       
      result++;
       
  }
       
 
       
  return result;
       
}
       
 
       
// ---------- second algorithm ----------

       
 
       
// O(n) algorithm, needs about 2 seconds for numLetters = 10^8

       
unsigned long long slow(unsigned long long numLetters)
       
{
       
  // state x means that currently x distinct letters were observed in the last x steps
       
  typedef std::array<unsigned long long, 7 + 1> State;
       
  // once we reach state 7 we have the word P,R,O,J,E,C,T (in any order) and remain in that state
       
  // no matter what follows
       
  State state = { 0 };
       
  state[0] = 1; // seed
       
 
       
  unsigned long long all = 1;
       
  for (unsigned long long i = 1; i <= numLetters; i++)
       
  {
       
    // total number of strings (regardless whether they contain PROJECT or not)
       
    all *= 7;
       
    all %= Modulo;
       
 
       
    State next = { 0 };
       
 
       
    // compute all state transitions
       
    next[1] = 7 * state[0] + 1 * state[1] + 1 * state[2] + 1 * state[3] + 1 * state[4] + 1 * state[5] + 1 * state[6];
       
    next[2] =                6 * state[1] + 1 * state[2] + 1 * state[3] + 1 * state[4] + 1 * state[5] + 1 * state[6];
       
    next[3] =                               5 * state[2] + 1 * state[3] + 1 * state[4] + 1 * state[5] + 1 * state[6];
       
    next[4] =                                              4 * state[3] + 1 * state[4] + 1 * state[5] + 1 * state[6];
       
    next[5] =                                                             3 * state[4] + 1 * state[5] + 1 * state[6];
       
    next[6] =                                                                            2 * state[5] + 1 * state[6];
       
    next[7] =                                                                                         + 1 * state[6];
       
 
       
    // once I'm in state 7 I stay there
       
    next[7] += 7 * state[7];
       
 
       
    // keep only the last 9 digits
       
    for (auto& x : next)
       
      x %= Modulo;
       
 
       
    state = std::move(next);
       
  }
       
 
       
  // state[7] represents the number of strings WITH the word "project"
       
  auto withProject = state[7];
       
  // without = all - with, but avoid negative results (due to modulo)
       
  if (all < withProject)
       
    all += Modulo;
       
  return all - withProject;
       
}
       
 
       
// ---------- third and final algorithm ----------

       
 
       
// quadratic 2D matrix

       
template <typename Number, unsigned int Size>
       
class Matrix
       
{
       
  // store all elements
       
  std::array<std::array<Number, Size>, Size> data; // same as Number data[Size][Size];
       
 
       
public:
       
  // set all elements to zero
       
  Matrix()
       
  : data()
       
  {
       
    for (unsigned int i = 0; i < Size; i++)
       
      data[i].fill(0);
       
  }
       
 
       
  // access a field (read/write), indices are zero-based
       
  Number& operator()(unsigned int column, unsigned int row)
       
  {
       
    return data[row][column];
       
  }
       
  // access a field (read-only), indices are zero-based
       
  Number get(unsigned int column, unsigned int row) const
       
  {
       
    return data[row][column];
       
  }
       
 
       
  // multiply two matrices
       
  Matrix operator*(const Matrix& other) const
       
  {
       
    Matrix result; // initially all fields are zero
       
    for (unsigned int i = 0; i < Size; i++)
       
      for (unsigned int j = 0; j < Size; j++)
       
        for (unsigned int k = 0; k < Size; k++)
       
          result(i,k) += get(j,k) * other.get(i,j);
       
    return result;
       
  }
       
 
       
  // fast exponentiation with modulo
       
  Matrix powmod(unsigned long long exponent, unsigned int modulo) const
       
  {
       
    // more or less the same concept as powmod from my toolbox (which works on integers instead of matrices)
       
 
       
    // start with identity matrix
       
    Matrix result;
       
    for (unsigned int i = 0; i < Size; i++)
       
      result(i,i) = 1;
       
    Matrix base = *this;
       
 
       
    while (exponent > 0)
       
    {
       
      // fast exponentation:
       
      // odd exponent ? a^b = a*a^(b-1)
       
      if (exponent & 1)
       
      {
       
        result = result * base;
       
 
       
        // modulo
       
        for (unsigned int i = 0; i < Size; i++)
       
          for (unsigned int k = 0; k < Size; k++)
       
            result(i,k) = result(i,k) % modulo;
       
      }
       
 
       
      // even exponent ? a^b = (a*a)^(b/2)
       
      base = base * base;
       
 
       
      // modulo
       
      for (unsigned int i = 0; i < Size; i++)
       
        for (unsigned int k = 0; k < Size; k++)
       
          base(i,k) = base(i,k) % modulo;
       
 
       
      exponent >>= 1;
       
    }
       
    return result;
       
  }
       
};
       
 
       
// solve "almost instantly", too fast to measure execution time ...

       
unsigned long long fast(unsigned long long numLetters)
       
{
       
  // same concept as slow() but rewritten with Matrix
       
 
       
  // state transitions
       
  Matrix<unsigned long long, 8> mat;
       
  mat(0,0) = 0; mat(1,0) = 0; mat(2,0) = 0; mat(3,0) = 0; mat(4,0) = 0; mat(5,0) = 0; mat(6,0) = 0; mat(7,0) = 0;
       
  mat(0,1) = 7; mat(1,1) = 1; mat(2,1) = 1; mat(3,1) = 1; mat(4,1) = 1; mat(5,1) = 1; mat(6,1) = 1; mat(7,1) = 0;
       
  mat(0,2) = 0; mat(1,2) = 6; mat(2,2) = 1; mat(3,2) = 1; mat(4,2) = 1; mat(5,2) = 1; mat(6,2) = 1; mat(7,2) = 0;
       
  mat(0,3) = 0; mat(1,3) = 0; mat(2,3) = 5; mat(3,3) = 1; mat(4,3) = 1; mat(5,3) = 1; mat(6,3) = 1; mat(7,3) = 0;
       
  mat(0,4) = 0; mat(1,4) = 0; mat(2,4) = 0; mat(3,4) = 4; mat(4,4) = 1; mat(5,4) = 1; mat(6,4) = 1; mat(7,4) = 0;
       
  mat(0,5) = 0; mat(1,5) = 0; mat(2,5) = 0; mat(3,5) = 0; mat(4,5) = 3; mat(5,5) = 1; mat(6,5) = 1; mat(7,5) = 0;
       
  mat(0,6) = 0; mat(1,6) = 0; mat(2,6) = 0; mat(3,6) = 0; mat(4,6) = 0; mat(5,6) = 2; mat(6,6) = 1; mat(7,6) = 0;
       
  mat(0,7) = 0; mat(1,7) = 0; mat(2,7) = 0; mat(3,7) = 0; mat(4,7) = 0; mat(5,7) = 0; mat(6,7) = 1; mat(7,7) = 7;
       
  // note: I could have skipped all those mat(x,y) = 0 because all cell are initialized with zero anyway
       
 
       
  // exponentiate matrix
       
  auto superMatrix = mat.powmod(numLetters, Modulo);
       
 
       
  // the number of strings WITH the word "project" (number of ways to transition from state 0 to 7)
       
  auto withProject = superMatrix.get(0,7);
       
  // total number of combinations is 7^numLetters
       
  // => I could use powmod(7, 10^12, Modulo) from my toolbox, but there's a 7 in the lower-right corner of the matrix at 7,7
       
  //    and since it's exponated as well, it becomes (7^numLetters) % Modulo and that's just what I need
       
  auto all         = superMatrix.get(7,7); // and surprisingly 7^(10^12) % 10^9 = 1 !
       
 
       
  // without = all - with, but avoid negative results (due to modulo)
       
  if (all < withProject)
       
    all += Modulo;
       
  return all - withProject;
       
}
       
 
       
int main()
       
{
       
  unsigned long long limit = 1000000000000ULL; // 10^12
       
  std::cin >> limit;
       
  //std::cout << bruteForce(limit) << std::endl;
       
  //std::cout << slow(limit) << std::endl;
       
  std::cout << fast(limit) << std::endl;
       
  return 0;
       
}

This solution contains 37 empty lines, 54 comments and 2 preprocessor commands.