get Nth number generated by rand() in O(1)

I have already seen this and this. It does not really solve my problem.

A simple implementation of standard glibc rand function is given here.

#include <stdio.h>

#define MAX 1000
#define seed 1

main() {
  int random_numbers[MAX];
  int i;

  random_numbers[0] = seed;
  for (i=1; i<31; i++) {
    random_numbers[i] = (16807LL * r[i-1]) % 2147483647;
    if (random_numbers[i] < 0) {
      random_numbers[i] += 2147483647;
    }
  }
  for (i=31; i<34; i++) {
    random_numbers[i] = random_numbers[i-31];
  }
  for (i=34; i<344; i++) {
    random_numbers[i] = random_numbers[i-31] + random_numbers[i-3];
  }
  for (i=344; i<MAX; i++) {
    random_numbers[i] = random_numbers[i-31] + random_numbers[i-3];
    printf("%d\n", ((unsigned int)random_numbers[i]) >> 1);
  }
}

The algorithm is trivial: given a seed it generates first 31 numbers by multiplying the seed and taking mod of 2^31. Each of the following number i is the sum of i-31 + i-3.

I need to somehow get the value of the Nth number in a constant time. The idea is quite simple.

n100 = n97+n69;

n100 = n96 + n66 + n69;

n100 = n96 + 2*n66 + n38;

...

So, at some point I will get a polynomial

n100 = ai * ni for i = [0; 31], where ai are some integer coefficients.

I wrote a function that returns the ai-s for a given index i:

vector<size_t> GetCoefficients(size_t index) {
    vector<size_t> coeffs(34);
    stack<size_t> indices;

    indices.emplace(index - 31);
    indices.emplace(index - 3);

    while (!indices.empty()) {
        const auto current = indices.top();
        indices.pop();

        if (current < 31) {
            ++coeffs[current];
        } else if (current < 34) {
            ++coeffs[current - 31];
        } else {
            indices.emplace(current - 31);
            indices.emplace(current - 3);
        }
    }

    return coeffs;
}

It works all right for small values (up to a few hundreds) but takes forever on larger indices. I need to somehow decompose very large indices (1e7) so that I could predict the n-th output given the initial seed. Any tips?