Background

Description

输入一个整数 n，输出 n 拆分成若干正整数和的所有方案，即 n=S 1 +S 2 +…+S k 的形式，且S 1 ≤S 2 ≤…≤S k ，n≤20，请按照字典序输出。

Format

Input

一行一个整数 n。

Output

若干行，每行一个等式（数与数之间要求非降序排列）。最后一行给出解的总个数

Samples

4

1+1+1+1
1+1+2
1+3
2+2
4
total=5

10

1+1+1+1+1+1+1+1+1+1
1+1+1+1+1+1+1+1+2
1+1+1+1+1+1+1+3
1+1+1+1+1+1+2+2
1+1+1+1+1+1+4
1+1+1+1+1+2+3
1+1+1+1+1+5
1+1+1+1+2+2+2
1+1+1+1+2+4
1+1+1+1+3+3
1+1+1+1+6
1+1+1+2+2+3
1+1+1+2+5
1+1+1+3+4
1+1+1+7
1+1+2+2+2+2
1+1+2+2+4
1+1+2+3+3
1+1+2+6
1+1+3+5
1+1+4+4
1+1+8
1+2+2+2+3
1+2+2+5
1+2+3+4
1+2+7
1+3+3+3
1+3+6
1+4+5
1+9
2+2+2+2+2
2+2+2+4
2+2+3+3
2+2+6
2+3+5
2+4+4
2+8
3+3+4
3+7
4+6
5+5
10
total=42

15

1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
1+1+1+1+1+1+1+1+1+1+1+1+1+2
1+1+1+1+1+1+1+1+1+1+1+1+3
1+1+1+1+1+1+1+1+1+1+1+2+2
1+1+1+1+1+1+1+1+1+1+1+4
1+1+1+1+1+1+1+1+1+1+2+3
1+1+1+1+1+1+1+1+1+1+5
1+1+1+1+1+1+1+1+1+2+2+2
1+1+1+1+1+1+1+1+1+2+4
1+1+1+1+1+1+1+1+1+3+3
1+1+1+1+1+1+1+1+1+6
1+1+1+1+1+1+1+1+2+2+3
1+1+1+1+1+1+1+1+2+5
1+1+1+1+1+1+1+1+3+4
1+1+1+1+1+1+1+1+7
1+1+1+1+1+1+1+2+2+2+2
1+1+1+1+1+1+1+2+2+4
1+1+1+1+1+1+1+2+3+3
1+1+1+1+1+1+1+2+6
1+1+1+1+1+1+1+3+5
1+1+1+1+1+1+1+4+4
1+1+1+1+1+1+1+8
1+1+1+1+1+1+2+2+2+3
1+1+1+1+1+1+2+2+5
1+1+1+1+1+1+2+3+4
1+1+1+1+1+1+2+7
1+1+1+1+1+1+3+3+3
1+1+1+1+1+1+3+6
1+1+1+1+1+1+4+5
1+1+1+1+1+1+9
1+1+1+1+1+2+2+2+2+2
1+1+1+1+1+2+2+2+4
1+1+1+1+1+2+2+3+3
1+1+1+1+1+2+2+6
1+1+1+1+1+2+3+5
1+1+1+1+1+2+4+4
1+1+1+1+1+2+8
1+1+1+1+1+3+3+4
1+1+1+1+1+3+7
1+1+1+1+1+4+6
1+1+1+1+1+5+5
1+1+1+1+1+10
1+1+1+1+2+2+2+2+3
1+1+1+1+2+2+2+5
1+1+1+1+2+2+3+4
1+1+1+1+2+2+7
1+1+1+1+2+3+3+3
1+1+1+1+2+3+6
1+1+1+1+2+4+5
1+1+1+1+2+9
1+1+1+1+3+3+5
1+1+1+1+3+4+4
1+1+1+1+3+8
1+1+1+1+4+7
1+1+1+1+5+6
1+1+1+1+11
1+1+1+2+2+2+2+2+2
1+1+1+2+2+2+2+4
1+1+1+2+2+2+3+3
1+1+1+2+2+2+6
1+1+1+2+2+3+5
1+1+1+2+2+4+4
1+1+1+2+2+8
1+1+1+2+3+3+4
1+1+1+2+3+7
1+1+1+2+4+6
1+1+1+2+5+5
1+1+1+2+10
1+1+1+3+3+3+3
1+1+1+3+3+6
1+1+1+3+4+5
1+1+1+3+9
1+1+1+4+4+4
1+1+1+4+8
1+1+1+5+7
1+1+1+6+6
1+1+1+12
1+1+2+2+2+2+2+3
1+1+2+2+2+2+5
1+1+2+2+2+3+4
1+1+2+2+2+7
1+1+2+2+3+3+3
1+1+2+2+3+6
1+1+2+2+4+5
1+1+2+2+9
1+1+2+3+3+5
1+1+2+3+4+4
1+1+2+3+8
1+1+2+4+7
1+1+2+5+6
1+1+2+11
1+1+3+3+3+4
1+1+3+3+7
1+1+3+4+6
1+1+3+5+5
1+1+3+10
1+1+4+4+5
1+1+4+9
1+1+5+8
1+1+6+7
1+1+13
1+2+2+2+2+2+2+2
1+2+2+2+2+2+4
1+2+2+2+2+3+3
1+2+2+2+2+6
1+2+2+2+3+5
1+2+2+2+4+4
1+2+2+2+8
1+2+2+3+3+4
1+2+2+3+7
1+2+2+4+6
1+2+2+5+5
1+2+2+10
1+2+3+3+3+3
1+2+3+3+6
1+2+3+4+5
1+2+3+9
1+2+4+4+4
1+2+4+8
1+2+5+7
1+2+6+6
1+2+12
1+3+3+3+5
1+3+3+4+4
1+3+3+8
1+3+4+7
1+3+5+6
1+3+11
1+4+4+6
1+4+5+5
1+4+10
1+5+9
1+6+8
1+7+7
1+14
2+2+2+2+2+2+3
2+2+2+2+2+5
2+2+2+2+3+4
2+2+2+2+7
2+2+2+3+3+3
2+2+2+3+6
2+2+2+4+5
2+2+2+9
2+2+3+3+5
2+2+3+4+4
2+2+3+8
2+2+4+7
2+2+5+6
2+2+11
2+3+3+3+4
2+3+3+7
2+3+4+6
2+3+5+5
2+3+10
2+4+4+5
2+4+9
2+5+8
2+6+7
2+13
3+3+3+3+3
3+3+3+6
3+3+4+5
3+3+9
3+4+4+4
3+4+8
3+5+7
3+6+6
3+12
4+4+7
4+5+6
4+11
5+5+5
5+10
6+9
7+8
15
total=176

Limitation

1s, 1024KiB for each test case.