Cho một xâu ~s~ chỉ chứa các chữ số từ 0 đến 9 và có độ dài không quá ~30~ kí tự. Ta biết rằng mỗi số từ ~1~ đến ~26~ có thể được ánh xạ thành một chữ cái từ ~A~ đến ~Z~, ví dụ như ~1 \rightarrow~ A, ~2 \rightarrow~ B, ..., ~26 \rightarrow~ Z.

Yêu cầu

Em hãy viết chương trình in ra số cách mà xâu ~s~ có thể được giải mã thành một chuỗi chữ cái hợp lệ.

Lưu ý: Nếu ký tự 0 xuất hiện riêng một mình thì xâu đó không thể được giải mã. Ví dụ: ~s =~ 01 thì kết quả là ~0~.

Dữ liệu đầu vào

Gồm xâu kí tự ~s~ chỉ chứa các kí tự từ 0 đến 9.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số cách mà xâu ~s~ có thể được giải mã thành một chuỗi chữ cái hợp lệ.

Ví dụ

Ví dụ 1

INPUT

121

OUTPUT

3

Giải thích: Với ~s =~ 121, có ~3~ cách giải mã:

• 1 2 1 ~\rightarrow~ ABA;
• 12 1 ~\rightarrow~ LA;
• 1 21 ~\rightarrow~ AU.

Ví dụ 2

INPUT

10

OUTPUT

1

Giải thích: Với ~s =~ 10, chỉ có cách duy nhất là 10 ~\rightarrow~ J.