# coding=utf-8
# 
# Solution to Project Euler problem 618
# Philippe Legault
# 
# https://github.com/Bathlamos/Project-Euler-Solutions

from lib import primes_up_to

# Use dynamic programming to keep the product of all all collections of prime whose sums equal to the index
# Build one prime at a time, in ascending order, to prevent duplicates
def compute():
	f = fibonacci_sequence(24)
	limit = f[-1]
	primes = primes_up_to(limit)
	cache = [0 for i in xrange(0, limit + 1)]
	compute_sum_prime_factors(cache, primes, 0, limit)
	return sum(cache[a] for a in f[1:]) % 10**9

def compute_sum_prime_factors(cache, primes, prime_index, target):
	for p in primes:
		cache[p] += p
		for i in xrange(1, target + 1 - p):
			cache[i + p] = int((cache[i + p] + cache[i] * p) % 10**9)
	return cache[target]

def fibonacci_sequence(n):
	if n == 1:
		return [1]
	a, b = 1, 1
	res = [a, b]
	for i in range(2, n):
		c = a + b
		a = b
		b = c
		res.append(b)
	return res
	

if __name__ == "__main__":
	print(compute())