Cho số nguyên dương ~n~. Mỗi dãy số nguyên dương không giảm có tổng bằng ~n~ được gọi là một cách phân tích số ~n~.

Yêu cầu: Hãy liệt kê các cách phân tích số ~n~ theo thứ tự từ điển.

Ví dụ với ~n = 5~ ta có ~7~ cách phân tích:

• ~5 = 1 + 1 + 1 + 1 + 1~
• ~5 = 1 + 1 + 1 + 2~
• ~5 = 1 + 1 + 3~
• ~5 = 1 + 2 + 2~
• ~5 = 1 + 4~
• ~5 = 2 + 3~
• ~5 = 5~

Input

• Gồm một dòng chứa số nguyên dương ~n~ ~(n \le 50)~.

Output

• Mỗi dòng in ra một cách phân tích: các phần tử của dãy số theo đúng thứ tự, cách nhau bởi dấu cách.
• Dòng cuối cùng in ra số cách phân tích.

Sample Input

5

Sample Output

1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
1 4
2 3
5
7