2288 - 质数组成
Description

给出一个数字N,我们认为任意一个数字都可以用若干个质数构成它,例如8=2+2+2+2,也可以是8=3+5,现在让你求出组成N的质数方案数!

数字可以重复用,2 3 5,和3 2 5,我们认为是两种不同的方案!

Input

一个数字N

Output

方案数,如果无法构成,请输出0

Examples

Input

8

Output

6
Hint

0\leq N \leq 50

题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 59
通过次数 7