Ngân và Huy cần gửi tin nhắn bí mật cho nhau và đang thảo luận về cách mã hóa tin nhắn của họ. Sau đây là phần họ thảo luận:

Ngân: Hãy sử dụng một mã rất đơn giản: Chúng ta sẽ gán \(A\) từ mã \(1\), \(B\) sẽ là \(2\), và cứ thế xuống \(Z\) được gán \(26\).

Huy: Đây là một mã ngu ngốc, Ngân. Giả sử tôi gửi cho bạn từ \(BEAN\) được mã hóa thành \(25114\). Bạn có thể giải mã điều đó theo nhiều cách khác nhau!

Ngân: Chắc chắn bạn có thể, nhưng bạn sẽ nhận được từ nào? Khác với \(BEAN\), bạn sẽ nhận được \(BEAAD\), \(YAAD\), \(YAN\), \(YKD\) và \(BEKD\). Tôi nghĩ rằng bạn sẽ không thể tìm ra giải mã chính xác. Và tại sao bạn lại gửi cho tôi từ \(BEAN\)?

Huy: Có thể đó là một ví dụ tồi, nhưng tôi cá với bạn rằng nếu bạn có một chuỗi có độ dài \(5000\) thì sẽ có hàng tấn giải mã khác nhau và bạn sẽ tìm thấy ít nhất hai cái khác nhau có ý nghĩa.

Ngân: Vậy có bao nhiêu cách giải mã khác nhau?

Huy: Jillions!

Vì một số lý do, Ngân vẫn không bị thuyết phục bởi lập luận của Huy, vì vậy cô ấy yêu cầu một chương trình sẽ xác định có bao nhiêu giải mã có thể có cho một chuỗi sử dụng cách mã hoá như trên.

Dữ liệu vào

• Đầu vào sẽ bao gồm nhiều bộ đầu vào.
• Mỗi bộ sẽ bao gồm một dòng duy nhất có tối đa \(5000\) chữ số thể hiện mã hóa hợp lệ (ví dụ: không có dòng nào bắt đầu bằng \(0\)). Sẽ không có khoảng cách giữa các chữ số.
• Một dòng đầu vào \(0\) sẽ chấm dứt đầu vào và không được xử lý.

Dữ liệu ra

• Đối với mỗi bộ đầu vào, hãy xuất số lượng giải mã có thể có cho chuỗi đầu vào.

Input 1

25114
1111111111
3333333333
0

Output 1

6
89
1