Palindromic Decomposition

Given an integer ( n ), find all possible palindromic decompositions of its decimal representation. A palindromic decomposition of ( n ) is a splitting of the string representation of ( n ) into substrings such that each substring is a palindrome.

For example, if ( n = 121 ), then its string representation is "121" and there are two palindromic decompositions:
1. "1", "2", "1"
2. "121"

Your task is to output the total number of decompositions on the first line, and then each decomposition on separate lines with the palindromic substrings separated by a single space. The order of decompositions should follow the natural order of recursive exploration.

inputFormat

The input consists of a single integer ( n ) provided via standard input.

outputFormat

On the first line, output the total number of palindromic decompositions. Then, for each decomposition, output a line containing the palindromic substrings separated by a single space. The order of the decompositions should be the same as produced by a standard recursive backtracking algorithm.## sample

121

2
1 2 1
121