즐거운 수

스웨덴 청소년 프로그래밍 국가대표팀은 여행을 다닐 때 즐겁게 지내는 것을 좋아한다. 그 누구보다 즐거움을 중시한 사람은 Mårten이었다. 하지만 그가 생각하는 즐거움은 다른 모든 사람이 생각하는 즐거움과 달랐다. Mårten에게 즐거움은 순전히 수학적으로 정의되었다. 어떤 수가 3로 나누어떨어질 때, 그리고 그럴 때에만 그 수는 즐거운 수이다.

모든 수가 즐거운 것은 아니므로, 당연히 수를 즐겁게 만드는 방법을 찾아야 한다. 정수 하나가 주어질 때, 수의 일부 숫자를 지워 그 수를 즐거운 수로 만들 수 있는 방법의 수를 Mårten이 계산하도록 돕는 것이 여러분의 임무이다. 단, 모든 숫자를 지울 수는 없으며, 만들어진 수에 앞에 붙은 영이 있어서는 안 된다. 다만 수 $0$은 즐거운 수로 간주되므로 영 하나만 남는 것은 괜찮다. 어떤 수의 각 자리 숫자의 합이 삼으로 나누어떨어질 때, 그리고 그럴 때에만 그 수가 삼으로 나누어떨어진다는 점을 기억하라.

점수

여러 테스트 케이스 그룹으로 여러분의 풀이를 테스트한다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

$1$ |$20$| $N \leq 6$이고 답은 십억보다 작다

$2$ |$20$| $N \leq 20$이고 답은 십억보다 작다

$3$ |$20$| $N \leq 1000$

$4$ |$40$| 추가 제한 없음

입력의 처음이자 유일한 줄에 정수 하나가 주어진다. 이 정수는 최대 $100\,000$개의 숫자로 이루어진다. 수에는 $0$-$9$의 숫자만 들어 있다. 수는 영으로 시작하지 않는다.

Mårten이 수에서 숫자를 지워 $3$로 나누어떨어지게 만들 수 있는 서로 다른 방법의 수 하나를 한 줄에 출력한다. 숫자를 지운 위치의 인덱스가 다르면 두 방법은 서로 다른 것으로 간주한다. 답이 매우 커질 수 있으므로, 답을 십억으로 나누었을 때의 나머지를 출력해야 한다.

예제 1 설명: Mårten은 수에서 일이라는 숫자를 지우는 한 가지 방법으로 수를 나누어떨어지게 만들 수 있다. 그러면 수 3만 남으며, 이 수는 당연히 삼으로 나누어떨어진다.

예제 2 설명: Mårten은 어떤 숫자도 지우지 않아 수를 나누어떨어지게 만든다.

예제 3 설명: Mårten이 무엇을 하더라도 즐거운 수를 만들 수 없다.

예제 4 설명: 즐거운 수 9, 192, 912, 12를 만들 수 있지만, 마지막 수는 두 가지 방법으로 만들 수 있다. 처음 두 숫자를 지우거나 가운데 두 숫자를 지우면 된다.

예제 5 설명: 즐거운 수 0, 3, 12, 102, 123, 1023를 만들 수 있다.