Splitting a Natural Number

Problem Background

Special for beginners, ^_^

Problem Description

Any natural number $n\;(1\lt n\le 25)$ greater than $1$ can always be split into a sum of several natural numbers smaller than $n$. Given a natural number $n$, you are to find all the ways to split $n$ into a sum of numbers. In each split, the numbers are sorted in ascending order. Output these splits with the lexicographically smallest sequence printed first.

Input Format

The natural number $n$ to be split.

Output Format

Several addition expressions.

Sample Input

7

Sample Output

1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4

Constraints

1s, 1024KiB for each test case.

Hint

Think about how to reduce a problem of size $n$ into a smaller subproblem.