Partition of a Natural Number

Problem Description

Any natural number $n$ greater than $1$ can always be partitioned into a sum of several natural numbers smaller than $n$. Now given a natural number $n$, you are asked to partition $n$ into a sum of numbers. In each partition the numbers are sorted in ascending order, and you must output these partitions, with the lexicographically smaller partitions output first.

Input Format

Input: the natural number $n$ to be partitioned.

Output Format

Output: several addition expressions.

Sample Input 1

7

Sample Output 1

7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4

Constraints

The data guarantees $2 \le n \le 8$.