삼각수의 개수를 제한하지 않으면 임의의 자연수를 훨씬 더 다양하게 삼각수들의 합으로 표현할 수 있다. 예를 들면, 다음과 같이 4, 5, 6은 각각 3, 4, 7가지 방법으로 표현할 수 있다.



4 = 1 + 1 + 1 + 1

= 1 + 3

= 3 + 1



5 = 1 + 1 + 1 + 1 + 1

= 1 + 1 + 3

= 1 + 3 + 1

= 3 + 1 + 1



6 = 1 + 1 + 1 + 1 + 1 + 1

= 1 + 1 + 1 + 3

= 1 + 1 + 3 + 1

= 1 + 3 + 1 + 1

= 3 + 1 + 1 + 1

= 3 + 3

= 6


여러분들이 할 일은 자연수 n이 입력으로 주어질 때,  n을 삼각수들의 합으로 표현할 수 있는 방법을 모두 찾는 것이다.프로그램의 실행시간은 1.0초를 초과할 수 없다.


입력 형식

표준 입력을 통하여 입력한다. 첫째 줄에 양의 정수 n 과 정수 p 가 순서대로 입력된다. p = 1이면 항상 n 이다.


출력 형식

표준 출력을 통하여 출력한다. 첫째 줄에 n을 삼각수들의 합으로 표현할 수 있는 방법의 개수를 10^6으로 나눈 나머지를 출력한다. 만약 p = 1이라면 추가로 둘째 줄부터 마지막 줄까지  n 을 삼각수들의 합으로 표현하는 방법을 한 줄에 하나씩 사전식 순서로 출력한다. 이 때, 덧셈 기호를 생략하고 대신에 빈칸 하나를 넣는다.


입력과 출력의 예 (1)

입력

4 1


출력

3

1 1 1 1

1 3

3 1


입력과 출력의 예 (2)

입력

5 -1


출력

4




동적할당인줄 알고 접근했는데 시간초과네요...ㅜㅜ


짠 코드는 https://slexy.org/view/s215x7G7XU 이거임니다