A + B = C

정보 올림피아드의 연습 대회에서는 주어진 정수 $A$와 $B$의 합을 구하는 "A + B" 문제가 자주 출제된다.

시 정보 올림피아드를 준비하던 출제 위원장은 이런 문제의 테스트를 직접 만들기로 했다. 그는 독특한 방법을 사용했는데, 먼저 정답으로 삼을 값을 정하고 그 값에 맞는 입력을 만드는 것이었다.

위원장이 $n$자리 십진수이고 맨 앞 자리가 0이 아닌 수 $C$를 골랐다고 하자. 이제 그는 합이 $C$가 되면서 각각 $n$자리 십진수이고 맨 앞 자리가 0이 아닌 양의 정수 $A$와 $B$를 찾으려 한다. 게다가 위원장은 $A$와 $B$가 모두 아름다운 수가 되도록 하려 한다. 그가 생각하는 아름다운 수란, 같은 숫자가 연속으로 두 번 나오지 않는 수이다. 예를 들어 $1272$는 아름다운 수이고 $1227$은 아니다.

자연수 $C$가 주어질 때, 합이 $C$인 아름다운 양의 정수 쌍 $A, B$의 개수를 구하는 프로그램을 작성하시오. 개수가 매우 클 수 있으므로 $10^9+7$로 나눈 나머지를 출력한다.

입력 파일에는 양의 정수 $C$가 하나 주어진다. $C$는 0으로 시작하지 않는다. $C$의 자릿수는 $10\,000$을 넘지 않는다.

출력 파일에는 아름다운 수 쌍 $A, B$의 개수를 $10^9+7$로 나눈 나머지를 나타내는 정수 하나를 출력한다.

$22$는 두 자리 수의 합으로 세 가지 방법으로 나타낼 수 있다: $10 + 12$, $11 + 11$, $12 + 10$. $11 + 11$은 $11$이 아름다운 수가 아니므로 제외된다. 따라서 $22$의 답은 $2$이다.

$200$은 세 자리 수의 합으로 $100 + 100$ 한 가지 방법으로만 나타낼 수 있다. 이 방법은 조건에 맞지 않으므로 $200$의 답은 $0$이다.

$1000$은 네 자리 수의 합으로 나타낼 수 없으므로 $1000$의 답도 $0$이다.