16400번 - 소수 화폐

소수나라는 특이하게 모든 소수(prime number)를 화폐 단위로 사용한다.

소수나라에 놀러 온 하나는 관광을 하다가 가격이 N인 물건을 발견하고 너무 마음에 들어 999983원을 내고 구매하려고 했다. 하지만 상점 주인이 거스름돈이 없어 정확히 N원을 지불해달라고 하였다.

물건을 구매하려던 하나는 소수나라의 화폐를 이용하여 N원을 정확히 만들 수 있는 방법의 가짓수가 얼마나 되는지 궁금해졌다.

하나를 도와 N원을 지불하기 위한 가짓수가 얼마나 되는지 구해보자.

단, 하나는 소수나라의 모든 화폐가 무한정 있다고 가정한다.

구매하려고하는 물건의 값 N(2 ≤ N ≤ 40,000, N은 정수)이 주어진다.

소수나라의 화폐를 이용하여 지불할 수 있는 방법의 수를 출력한다.

단, 지불할 수 있는 방법의 수가 매우 크기때문에, 123,456,789로 나눈 나머지 값을 출력한다.

8원짜리 물건은 아래와 같이 3가지 방법으로 구할 수 있다.

1. 2원 4개

2. 2원 1개, 3원 2개

3. 3원 1개, 5원 1개