문제

다다스 중학교 선생님 이성원은 개의 책을 개의 책장에 나누어 정리하려 한다. 모든 책장은 적어도 한 권 이상의 책을 가져야 하며, 이때, 책의 순서는 고려 안해도 된다. 이때, 책을 나누는 서로 다른 방법의 수를 로 나눈 나머지를 구하는 프로그램을 작성해보자!

입력

정수 가 입력된다. ( )

출력

책을 나누는 서로 다른 방법의 수를 로 나눈 나머지를 출력한다.