소수 화폐

면접 대비

시간 제한1초메모리 제한256 MB

요약

소수 화폐를 원하는 개수로 써서 N원을 만드는 주문서 수를 구해 123,456,789로 나눈 나머지를 출력합니다.

문제

소수나라는 모든 소수를 화폐 단위로 사용한다.

소수나라에 놀러 온 하나는 가격이 N인 물건을 발견하고 999983원을 내고 사려고 했다. 하지만 상점 주인은 거스름돈이 없어 정확히 N원을 내라고 했다.

하나는 소수나라의 화폐로 N원을 정확히 만들 수 있는 방법이 몇 가지인지 궁금해졌다. 하나를 도와 N원을 지불하는 방법의 수를 구하자.

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

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

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

단, 방법의 수가 매우 크므로 123,456,789로 나눈 나머지를 출력한다.

8원짜리 물건은 다음 3가지 방법으로 살 수 있다.