진법 표기 복원

모든 음이 아닌 정수는 숫자들의 나열로 나타낼 수 있다. 가장 널리 쓰이는 체계는 열 개의 숫자를 사용하는 십진법(밑수 10)이다. 이 외에 다른 밑수를 쓰는 체계도 있는데, 예를 들어 컴퓨터에서는 이진법(밑수 2)이 자주 쓰인다.

일반적으로 밑수가 $r$($r > 1$)인 체계에서 음이 아닌 정수 $n$을 숫자열

$$d_k,d_{k-1},\cdots,d_1,d_0$$

으로 적으면, 그 값은

$$n = d_k \cdot r^{k} + d_{k-1} \cdot r^{k-1} + \cdots + d_1 \cdot r + d_0$$

이다. 모든 자리의 숫자는 밑수보다 작아야 한다. 즉, $0 \le i \le k$인 모든 $i$에 대해 $0 \le d_i < r$이다.

밑수가 10보다 크면 9를 넘는 "숫자"를 나타낼 기호가 더 필요하기 때문에 불편하다. 흔히 알파벳을 쓰지만 글자 수도 유한하므로 아주 큰 밑수는 이렇게 적을 수 없다.

또 다른 방법은 각 자리의 숫자를 그 자체로 십진수로 적는 것이다. 예를 들어 16진수 1A8D는 (1-10-8-13)16으로 적을 수 있다. 혼동을 막기 위해 (십진법이라도) 항상 밑수를 뒤에 붙인다. 이 글에서는 이 형식을 십진 부호화 표기(decimal-encoded notation) 라고 부른다.

십진 부호화 표기는 불필요한 0이 없을 때에만 올바른 표기로 인정한다. 구체적으로, 밑수나 어떤 자리의 숫자에도 불필요한 앞자리 0이 있어서는 안 되고(여러 자리로 이루어진 수의 최상위 자리는 0일 수 없고, 각 자리 숫자의 십진 표기 자체에도 앞자리 0이 없어야 하며, 밑수에도 앞자리 0이 없어야 한다), 모든 자리의 숫자는 밑수보다 작아야 한다. 예를 들어 (1-0-0-0)7, (4-7689)7690, (0)16은 올바르지만, (0-3-6)8, (1-02-3)6, (3-2-1)07, (9)6은 올바르지 않다.

이렇게 올바른 십진 부호화 표기로 저장된 수들이 파일에 담겨 있었는데, 버그로 인해 파일이 손상되었다. 십진 숫자는 모두 원래 순서 그대로 남았지만, 대시(-)와 괄호가 전부 사라졌다. 따라서 각 수는 십진 숫자만으로 이루어진 문자열이 되었고, 이런 문자열은 매우 모호해서 대부분 여러 수로 해석될 수 있다. 예를 들어 1234는 (1-2-3)4, (12)34, (1-2)34, (1)234 중 어느 것으로도 읽을 수 있다.

손상된 각 문자열에 대해, 그 문자열을 만들어 낼 수 있는 서로 다른 십진 부호화 표기가 몇 가지인지 구하여라. 두 표기는 값이 같더라도 서로 다른 것으로 센다.

입력은 여러 줄로 이루어진다. 각 줄에는 코드 하나, 즉 십진 숫자로 이루어진 문자열이 주어진다. 코드의 길이는 1 이상 35 이하이다. 입력의 마지막 줄에는 해시 문자 # 하나만 주어진다.

각 코드마다 한 줄을 출력한다. 그 코드를 만들어 내는 올바른 십진 부호화 표기가 하나도 없으면 The code CCC is invalid.를 출력한다. 그렇지 않으면 The code CCC can represent X numbers.를 출력한다. 이때 CCC는 주어진 코드로, X는 대시와 괄호를 지웠을 때 그 코드가 되는 서로 다른 십진 부호화 표기의 총 개수로 바꾼다. 표기는 값이 같더라도 서로 다른 것으로 센다.