반복 문제

아주 큰 문제가 생겼다. 당신은 점화식을 좋아하는데, 아마 조금 지나치게 좋아한다. 특히 양의 선형 점화식(PLRR)을 좋아한다. PLRR은 다음과 같이 정의한다. 먼저 차수 $k$를 고른다. 다음으로 계수 $c_1,c_2,\dots,c_k$와 수열의 처음 $k$개 항 $a_1,a_2,\dots,a_k$를 고른다. 이 수들이 모두 양의 정수이면 그 점화식을 양의 점화식이라고 한다. 나머지 항은 다음 식으로 무한히 생성할 수 있다.

$a_{i+k} = c_1 \cdot a_i + c_2 \cdot a_{i+1} + \cdots + c_k \cdot a_{i+k-1}$ ($i \ge 1$).

피보나치 수열이 이 형태의 가장 유명한 점화식이지만, 이 밖에도 많은 점화식이 있다.

어제 당신은 가능한 모든 PLRR과 각각이 만드는 무한 수열을 인덱스 카드에 한 장씩 적었다. 카드는 대량으로 사 두었기 때문에 수가 많다.

수열을 그대로 사전순으로 정렬하면 1로 시작하는 수열이 너무 많아서 뒤쪽 카드에는 도달할 수 없다. 그래서 PLRR을 생성된 부분만으로 사전순 정렬한다. 생성된 부분은 처음 $k$개 항 뒤에 이어지는 부분이다. 생성된 부분이 같으면 계수를 사전순으로 비교해 순서를 정한다. 예를 들어 $k=1$, $c_1=2$, $a_1=2$인 카드는 $k=2$, $(c_1,c_2)=(2,1)$, $(a_1,a_2)=(1,2)$인 카드보다 앞에 온다. 두 카드가 생성하는 이후 항은 같지만 그렇다. 카드는 1번부터 번호가 붙는다.

카드의 번호가 주어지면, 그 카드에 적힌 수열을 설명하라.

입력은 한 줄이며, 구하려는 PLRR의 번호 $n$ ($1 \le n \le 10^9$)이 주어진다.

네 줄을 출력한다. 첫째 줄은 차수 $k$이다. 둘째 줄은 $k$개의 계수 $c_1,\dots,c_k$이다. 셋째 줄은 $k$개의 시작값 $a_1,\dots,a_k$이다. 넷째 줄은 생성된 값의 처음 10개이다.