题目描述

任何大于 1 的自然数 N，都可以写成若干个大于等于2且小于等于 N 的质数之和表达式(包括只有一个数构成的和表达式的情况)，并且可能有不止一种质数和的形式。例如9 的质数和表达式就有四种本质不同的形式：9 = 2+5+2 = 2+3+2+2 = 3+3+3 = 2+7 。 这里所谓两个本质相同的表达式是指可以通过交换其中一个表达式中参加和运算的各个数的位置而直接得到另一个表达式。 试编程求解自然数 N 可以写成多少种本质不同的质数和表达式。

输入格式

读入一个自然数 N , 2≤N≤1070。

输出格式

依次输出每一个自然数 N 的本质不同的质数和表达式的数目。

输入输出样例

输入 #1

2

输出 #1

1

说明/提示

对于40%的数据 N<=200

对于100%的数据 N<=1070

要求本题提交代码长度不超过2KB，即不允许打表。保证输出答案在long long范围内