'use strict';

const PE = require('../pe_helper');

const fib    = PE.fibonacci(24);
const primes = PE.primeList(fib[24]);

const z_memo_map = new Uint32Array((fib[24] + 1) * primes.length);

function makeKey(n, k) {
    return (fib[24] + 1) * k + n;
}

for (let n = 0; n <= fib[24]; n++) {
    for (let i = 0; i < primes.length; i++) {
        let key = makeKey(n, i);
        let p   = primes[i];

        if (n === 0) {
            z_memo_map[key] = 1;
            continue;
        }

        if (p > n) {
            if (i === 0) {
                z_memo_map[key] = 0;
                continue;
            }

            z_memo_map[key] = z_memo_map[makeKey(n, i - 1)];
            continue;
        }

        if (i === 0) {
            z_memo_map[key] = (p * z_memo_map[makeKey(n - p, i)]) % 1e9;
            continue;
        }

        z_memo_map[key] = (z_memo_map[makeKey(n - p, i)] * p + z_memo_map[makeKey(n, i - 1)]) % 1e9;
    }
}

let total = 0;

for (let i = 2; i < 25; i++) {
    total += (z_memo_map[makeKey(fib[i], primes.length - 1)]) % 1e9;
}

console.log(total % 1e9);