cho.sh
Notes
Loading...

Consecutive Prime Sum

Time limit

2s

Memory limit

128 MB

Problem

Given a positive integer N, count the number of ways to represent N as the sum of one or more consecutive prime numbers.

Consecutive primes mean adjacent numbers in the increasing sequence of prime numbers. A prime number cannot be used more than once in a sum, and a sum that skips a prime in the middle is not considered a sum of consecutive primes.

Input

The first line contains a positive integer N. (1 <= N <= 4,000,000)

Output

Print the number of ways to represent N as the sum of consecutive prime numbers.