소수의 합

소수란 약수가 $1$과 자기 자신 밖에 없는 $2$ 이상의 자연수를 말한다. 예를 들어, $2$, $3$, $5$, $97$과 같은 수들은 소수이고, $1$, $6$, $18$, $55$와 같은 수 들은 소수가 아니다.

$2$ 이상의 자연수 $N$이 주어졌을 때, $N$을 한 개 이상의 소수들의 합으로 나타내는 방법의 수를 구하여라. 여기서 덧셈의 순서만 다른 경우는 모두 한 가지로 센다.

예를 들면, $7 = 2 + 2 + 3 = 2 + 5 = 7$ 이므로 $N = 7$ 일 때의 답은 $3$이다. 여기서, $7$은 소수이므로 "$7$" 자체도 $7$을 소수의 합으로 표현하는 올바른 방법이다. "$2 + 5$"와 "$5 + 2$" 같은 경우에는 덧셈의 순서만 다른 경우이므로 한 가지로 센다.

입력 형식

첫째 줄에 정수 $N$이 주어진다. ($2 \le N \le 20\,000$)

출력 형식

$N$을 한 개 이상의 소수들의 합으로 나타나는 방법의 수를 첫째 줄에 출력하여라. 단, 답이 매우 클 수 있으므로 $1\,000\,000\,007$ ($=10^9+7$)로 나눈 나머지를 출력한다.

예제

7

3

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설