Các học trò của Giáo sư X đều biết rằng, mỗi khi làm đề thi mà bí bài thì Giáo sư sẽ cho bài toán truyền thống: Cho hai số A và B, hãy tính tổng của hai số đó.

Lần này Giáo sư muốn đổi phong cách một chút bằng cách phát biểu lại đề chút cho hứng thú: Cho một số nguyên dương C, hãy tìm hai số nguyên dương A và B sao cho C=A+B.

Tuy nhiên, sợ bài như này khó quá, các thí sinh không làm được nên Giáo sư phát biểu lại đề và thêm một số ràng buộc như sau:

Cho một số nguyên dương C có n chữ số, hãy đếm xem có bao nhiêu số nguyên dương A và B sao cho:

• A và B là những số nguyên dương có n chữ số (không được bắt đầu bằng chữ số 0)
• A+B=C
• A,B phải là những số đẹp. Một số gọi là đẹp nếu không có hai chữ số cạnh nhau mà giống hệt nhau. Ví dụ: 1221 không phải là số đẹp nhưng 1212 lại là một số đẹp.

Yêu cầu: Cho số C, hãy đếm xem có bao nhiêu cặp số nguyên dương A và B thỏa mãn yêu cầu của Giáo sư. Vì đáp án rất lớn nên chỉ cần đưa ra phần dư đáp số cho 1E9+7.

Input: Vào từ file văn bản APLUSB.INP gồm một dòng duy nhất chứa một số nguyên C (Số chữ số của C tối đa là 10.000 chữ số)

Output: Ghi ra file văn bản APLUSB.OUT một số nguyên duy nhất là số lượng cặp A,B tìm được theo yêu cầu đề bài.

Ví dụ:

C=23, có 4 cách phân tích là:

1. 10 + 13
2. 11 + 12
3. 12 + 11
4. 13 + 10

Tuy nhiên chỉ có 2 cách 1 và 4 được chấp nhận vì trong hai cách còn lại có số 11 có 2 chữ số liên tiếp giống nhau.

Giới hạn:

• 25% số test có C<1000
• 25% số test khác có C<10^6
• 50% số test còn lại không có ràng buộc gì thêm