let fibonacci = function(n) {
		let fib = [ 0 ];

		let f1 = 0;
		let f2 = 1;
		let ftmp = 0;

		for (let i = 0; i < n; i++) {
			fib.push(f2);
			ftmp = f2;
			f2 = f1 + f2;
			f1 = ftmp;
		}

		return fib;
	}

	let primeList = function(n) {
		let list = [];
		let primes = [];

		for (let i = 2; i <= n; i++) {
			if (!list[i]) {
				primes.push(i);

				if (i <= Math.sqrt(n)) {
					for (let j = i*i; j <= n; j += i) {
						list[j] = 1;
					}
				}
			}
		}

		return primes;
	}

const fib    = fibonacci(25);
const primes = primeList(fib[25]);

function start() {

	let sums = []
	let parZero = new Array(primes.length)
	parZero = parZero.map(() => 1)
	sums.push(parZero)
  let parOne = new Array(primes.length)
  sums.push(parOne)

    for (let i = 2; i <= fib[25]; i++) {
		  let par = new Array(primes.length)
      for (let j = 0; j < primes.length; j++) {
        let prime = primes[j]
			  if (i - prime < 0) break
			  par[j] = prime * sums[i - prime][j]
      }
		  for (let j = primes.length - 2; j >= 0; j--) {
			  par[j] = (par[j] + par[j + 1]) % 1e9
      }
		  sums.push(par)
    }
	return sums
}

let sums = start();

let ans = sums
let tot = 0
for(let i = 2; i <= 25; i++) {
  tot += sums[fib[i]][0]
  console.log(sums[fib[i]][0])
}
console.log(tot % 1e9)