2085번 - 진법

우리는 보통 10진법을 사용하지만 컴퓨터에서는 2, 8, 16진법이 사용된다. 그 외에도 여러 가지 진법을 생각해 볼 수 있다. 16진법의 경우에는 두 자리 수들을 알파벳 문자들로 나타내지만, 이 문제에서는 수 형태로 생각하기로 한다. 각각의 수들은 공백으로 구분하고, 전체를 괄호로 둘러 싼 다음에 그 뒤에는 진법을 적는다. 예를 들어 16진법으로 1A8D는 (1 10 8 13)16이 된다.

공백이나 괄호를 생략하면 전체가 숫자로 구성된 문자열이 된다. 위의 예는 11081316이 된다. 만약 수가 이와 같은 형태로 주어진다면, 여기에 공백과 괄호를 적절히 추가하면 여러 가지 방법으로 수를 표현할 수 있다. 예를 들어 1234는 네 가지로 표현할 수 있는데, 각각 (1 2 3)4, (12)34, (1 2)34, (1)234가 된다.

숫자로 된 문자열이 주어졌을 때, 가능한 표현 방법을 모두 구해내는 방법을 구하시오. 만약 실제 값이 같더라도 다른 형태로 표현된다면 여러 번 세도록 한다.

단, 표현 방법들 중 불필요한 0이 사용되는 경우는 세지 않는다. 예를 들어 (0 3 6)8, (1 02 3)6, (3 2 1)07은 세지 않는다.

첫째 줄에 숫자로 구성된 문자열이 주어진다. 그 길이는 35자를 넘지 않는다.

첫째 줄에 답을 출력한다.