장난감
시간 제한4초메모리 제한512 MB
주어진 n에 대해, 장난감 종류별 개수로의 분할 수가 정확히 n이 되는 전체 장난감 개수 m을 모두 구한다.
문제
Johnny는 장난감을 모은다. 그의 컬렉션에는 자동차, 트럭, 굴착기 등 여러 종류의 장난감이 많이 있을 수 있다. 같은 종류의 장난감을 여러 개 가질 수도 있는데, 예를 들어 트럭을 네 대 가지고 있다면 Johnny에게 그 네 대는 서로 구별되지 않는다.
Emma가 Johnny에게 장난감이 몇 개 있느냐고 물었다. 비밀을 밝히고 싶지 않았던 그는 수수께끼로 답했다(그에게는 흔한 일이다). 매일 내 장난감의 서로 다른 집합을 고른다면, n일 동안 놀 수 있다. 다시 말해, 어느 두 날에 대해서도 어떤 종류의 장난감 개수가 서로 다르다. 여기서 Johnny는 빈 집합도 올바른 집합으로 본다.
Emma는 이 답도, 이 수수께끼도 마음에 들지 않지만 Johnny가 장난감을 몇 개나 가지고 있는지 정말 궁금하다. 그녀가 너희에게 도움을 청했다. Johnny의 컬렉션에 있을 수 있는 장난감 개수의 모든 가능성을 구할 수 있겠는가?
입력
표준 입력의 첫째 줄이자 유일한 줄에 정수 n이 주어진다. (1 ≤ n ≤ 109)
출력
표준 출력의 첫째 줄에는 해의 개수 r, 즉 Johnny의 컬렉션에 있을 수 있는 장난감 개수의 가능성 수를 출력한다.
둘째 줄에는 Johnny의 컬렉션에 있을 수 있는 장난감 개수를 나타내는 r개의 정수가 엄격히 증가하는 순서로 주어진다.