Ugly Number timer 1s memory 64MB

어떤 숫자가 (2, 3, 5, 7) 중의 하나로 나누어 떨어지면 그 수를 "Ugly Numbers" 라고 부른다. 따라서 14는 Ugly하지만 13은 그렇지 않다. 또한 39는 Ugly이고 121는 Ugly하지 않다. 다만 0은 Ugly한 수라고 부른다. 물론 이는 음수에 대해서도 성립한다. -14와 -39는 Ugly Number라고 부른다.

당신은 모처럼 한가한 시간을 보내고 있었다. 그러던 중 "123456"이 적힌 종이를 발견하고, 이 숫자들 사이에 +나 - 부호를 넣어서 얼마나 많은 Ugly Number가 나오는지 궁금했다. 예를 들어 1 + 234 - 5 + 6 = 236 이 되어 이 수는 Ugly Number이다. 하지만 123 + 4 - 56 = 71 과 같이 수정하면 Ugly하지 않은 수가 나온다.

얼마나 다양한 경우가 나오는지 계산을 해 보았다. 이 경우 각 숫자들 사이에 +, -를 넣거나, 아무것도 넣지 않는 경우가 있으므로, D자리의 숫자가 있으면 3^(D-1) 가지의 경우가 생긴다. 이 숫자는 앞에 나오는 0을 무시하지 않는다. 즉 "01023"이 입력으로 들어오면 "01023", "0+1-02+3", "01-023" 모두 올바른 수식이다.

당신이 해야 할 일은 간단하다. 3^(D-1)가지의 경우 중에서 ugly number가 나오는 경우가 얼마나 되는지 구하여라.