Đếm cách giải mã

Hai bạn Alice và Bob mã hoá tin nhắn bằng cách thay mỗi chữ cái tiếng Anh in hoa bằng một số: A \(\to 1\), B \(\to 2\), ..., Z \(\to 26\), rồi viết liền các số lại với nhau, không có dấu cách. Chẳng hạn BEAN được mã hoá thành 25114.

Vì các số được viết liền nhau nên một dãy chữ số có thể được giải mã theo nhiều cách. Ví dụ 25114 có thể đọc là BEAAD, BEAN, BEKD, YAAD, YAN, YKD (tổng cộng \(6\) cách).

Cho một dãy chữ số, hãy đếm số cách giải mã nó thành một xâu chữ cái. Mỗi cách giải mã là một cách chia dãy thành các đoạn liên tiếp, mỗi đoạn là một số từ \(1\) đến \(26\) không có chữ số \(0\) ở đầu (ví dụ 06 không hợp lệ). Nếu không có cách giải mã nào thì đáp án là \(0\).

Input

Input gồm nhiều dòng, mỗi dòng là một dãy chữ số (không có dấu cách) cần giải mã, chữ số đầu tiên khác \(0\). Input kết thúc bằng một dòng chỉ chứa ký tự 0; dòng này không cần xử lý.

Output

Với mỗi dãy chữ số, in ra một dòng chứa số cách giải mã. Số cách có thể rất lớn nên cần in chính xác toàn bộ giá trị (không lấy dư).

Constraints

• Mỗi dãy có từ \(1\) đến \(5000\) chữ số.
• Số dãy trong một file input không vượt quá \(100\).

Sample Input

226
2626
1010
100
0

Sample Output

3
4
1
0

Explanation

• 226: 2|2|6, 22|6, 2|26 nên có \(3\) cách.
• 2626: 2|6|2|6, 26|2|6, 2|6|26, 26|26 nên có \(4\) cách.
• 1010: chỉ có 10|10.
• 100: 10|0 không hợp lệ vì 0 đứng riêng, còn 1|00 cũng không hợp lệ, nên không có cách nào.