题目描述

输入一个整数 $n$，将 $n$ 表示成若干个各不相同的素数的乘积。

求：有多少种不同的方案？答案对 $10^9 + 7$ 取模。

注：$5 = 2 + 3$ 和 $5 = 3 + 2$ 视为同一种方案。

输入格式

一个整数 $n$。

输出格式

输出一个整数，表示方案数对 $10^9 + 7$ 取模的结果。

样例

16

3

100

198

说明/提示

数据规模与约定

• 对于 $50\%$ 的数据，$n \le 200$
• 对于 $100\%$ 的数据，$10 \le n \le 2000$