Description

Problem Statement

You are given an integer $N.$ Your task is to find the number of ways to partition $N$ into a sum of prime numbers.

Note:$-$ A partition of single number is also considered as a partition.

Two partitions are considered different if they differ in the number of times a particular prime number is used. For example:$-5=2+3$ and $5=3+2$ are considered same partitions.

Since the answer can be very large, return the answer modulo ${10}^9+7.$

Input Format

The only input contains a single integer $N.$

Constraints

$2N{10}^4$

Output Format

Return an integer denoting the number of ways to partition the given integer $N.$