质因数分解

众所周知，输入一个n，把n拆分成若干质数之积的方案是唯一的

输入一个n，问把 $n$ 拆分若干个质数之和有多少种方案。

分拆出的质数可以相同，分拆出的质数不计顺序，$5 = 2 + 3$ 和 $5 = 3 + 2$算作一种方案。

因为方案数可能很大，所以只输出方案数模$10007$的结果即可。

输入描述

一行一个整数n。

输出描述

一行一个整数表示答案。

样例输入

10

样例输出

  5

样例解释

10 = 2 + 2 + 2 + 2 + 2
10 = 2 + 2 + 3 + 3
10 = 2 + 3 + 5
10 = 3 + 7
10 = 5 + 5

样例输入

100

样例输出

871

数据规模与约定

对于100%的数据，满足$2 \leq n \leq 50000$

对于30%的数据，满足$2 \leq n \leq 100$

对于70%的数据，满足$2 \leq n \leq 3000$