"APlusB" là một bài tập lập trình rất nổi tiếng, được sử dụng trong hầu hết các website online judge cũng như trong các ngày practice của các contest. Bài tập này yêu cầu học viên/thí sinh nhập vào hai số nguyên \(A,B\) và tính tổng \(C=A+B\).

Để chuẩn bị cho site online judge của riêng mình, Bờm chuẩn bị test cho bài "APlusB", quy trình sinh test của Bờm là: chọn trước số nguyên dương \(C\) rồi chọn cặp số nguyên dương \((A,B)\) sao cho \(A+B=C\). Tuy nhiên Bờm muốn bài "AplusB" trên site của mình phải có sự khác biệt, theo đó Bờm chỉ chọn các cặp số \(A,B\) có cùng số chữ số với \(C\); ngoài ra trong mỗi số \(A,B\) đều không có hai chữ số liền kề nào giống nhau.

Bờm muốn nhờ bạn lập trình xác định với số nguyên \(C\) đã chọn làm answer, có bao nhiêu cách chọn cặp \((A,B)\) là input.

Input

• Dòng \(1\): số nguyên dương \(C\) có không quá \(10,000\) chữ số

Output

• Dòng \(1\): số nguyên là phần dư khi chia cho \((10^9+7)\) của số lượng cách chọn.

Example

22

2