Kết thúc 2018, Chỉ còn vài ngày nữa là các sinh viên UTC sẽ được về quê sum vầy ăn cái tết ấm áp bên gia đình.

Để khuyến khích tinh thần học tập năm 2019 của các Sinh viên mạnh mẽ hơn năm cũ, Trường đại học giao thông vận tải quyết định phát quà tết thật ý nghĩa. Ai lấy đều háo hức đem những phần quà này về tặng gia đình.

Tuy nhiên chỉ có các sinh viên khoa CNTT của trường lại rất đặc biệt, họ rất thông minh, Vì vậy các gói quà của họ được thiết kế rất đặc biệt bị khóa mật khẩu. Để mở được món quà này, các sinh viên IT UTC cần phải giải mã được câu đố ghi trên trước mặt của gói quà, thật thú vị :D

Với mỗi gói quà, sẽ có một dòng tin nhắn số bao gồm các chữ số từ 0 đến 9 đã được mã hóa từ tin nhắn chữ nào đó.

Biết rằng các kí tự in hoa có thể chuyển sang một số theo quy tắc như sau:

• 'A' -> 1
• 'B' -> 2
• 'C' -> 3
• ...
• 'Z' -> 26

Nhiệm vụ cần làm của sinh viên là tính ra số lượng X các tin nhắn chữ có thể dịch ngược từ tin nhắn số đã cho theo điều kiện chuyển đổi trên trên. Và số dư của X với 10^9 + 7 cũng chính là mật mã của gói quà :) (X % 1000000007)

Nào các sinh viên IT hãy chứng tỏ khả năng của mình thôi :)

Input:

• Dòng duy nhất chứa dòng tin nhắn số có độ dài n (0 <= n <= 10^5)

Output:

• Dòng duy nhất chứa mật mã.

Example:

Input:

123

Output:

3

Giải thích: 123 có thể dịch ra "ABC" (1 2 3), "LC" (12 3) và AW (1 23)

Example 2:

Input:

30

Output:

0