Start: 2024-11-25 00:00:00

(24-25赛季)稠州常规赛12

End: 2024-11-28 00:00:00
Now  2025-09-26 08:25:34  类型: IOI  状态: Ended 

P3. 质数组成3
Description

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

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



Input

一个数字N

Output

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

Examples

Input

5

Output

2

Input

10

Output

2
Hint

N\leq 200

Submit

题目参数
Time Limit 1 second
Memory Limit 128 MB
Submit