Prime Currency

Interview

Time limit1sMemory limit256 MB

Summary

Count the unordered ways to make N with unlimited primes, using a coin-change DP, and print the count modulo 123,456,789.

Level: Medium6 of 10
Topics: Dynamic programming, Number theory, Math
Solved: No attempts yet

Problem

The country of Sosu uses every prime number as a currency unit.

Hana is visiting Sosu and finds an item priced at N. She likes it so much that she tries to buy it with 999983 won, but the shopkeeper has no change and asks her to pay exactly N won.

Hana wonders how many ways she can make exactly N won using the currency of Sosu. Help Hana find the number of ways to pay N won.

Hana is assumed to have an unlimited supply of every currency in Sosu.

Input

The price N of the item to buy is given (2 ≤ N ≤ 40,000, N is an integer).

Output

Print the number of ways to pay using the currency of Sosu.

The number of ways can be very large, so print it modulo 123,456,789.

Hint

An item priced at 8 won can be bought in the following 3 ways.

Four 2-won coins
One 2-won coin and two 3-won coins
One 3-won coin and one 5-won coin

Examples1

Example 1
Input
```
8
```
Expected output
```
3
```