#1135. APLUSB - LẠI LÀ BÀI TOÁN ĐẾM

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 tính tổng hai số: Cho hai số và , 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 , hãy tìm hai số nguyên dương và sao cho . 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ó chữ số, hãy đếm xem có bao nhiêu số nguyên dương và sao cho:

• và là những số nguyên dương có chữ số (không được bắt đầu bằng chữ số )
• 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ụ: không phải là số đẹp nhưng lại là một số đẹp.

Yêu cầu: Cho số , hãy đếm xem có bao nhiêu cặp số nguyên dương và 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 .

Dữ liệu vào:

• Gồm một dòng duy nhất chứa một số nguyên (Số chữ số của tối đa là chữ số).

Dữ liệu ra:

• Một số nguyên duy nhất là số lượng cặp tìm được theo yêu cầu đề bài (kết quả được chia cho lấy phần dư).

Ví dụ:

Dữ liệu vào:

23

Dữ liệu ra:

2

Giải thích:

• Có cặp thỏa mãn là và

Dữ liệu vào:

100

Dữ liệu ra:

0

Giới hạn:

• số test có
• số test khác có
• số test còn lại không có ràng buộc gì thêm