~2048~ là một trò chơi đơn giản nhưng vô cùng cuốn hút và cũng không kém phần thử thách. Nhiều game thủ đã dành nhiều giờ hay thậm chí là nhiều ngày chỉ để hoàn thành trò chơi này một lần.

DeMen100ns có một số nguyên dương ~n~. Tuy nhiên một số vị trí trong số ~n~ đã biến mất và được thay bằng ký tự "~?~".

DeMen100ns muốn biết có bao nhiêu cách điền các chữ số vào tất cả các ký tự "~?~" để ~n~ chia hết cho ~2048~? Vì DeMen100ns đang bận hoàn thành trò chơi ~2048~, hãy giúp cậu ấy trả lời câu hỏi trên.

Input

• Một dòng duy nhất là xâu ký tự biểu diễn số ~n~ (~1 \le n \le 10^{10^5}~). Mỗi ký tự trong xâu là một chữ số hoặc một dấu "~?~", ký tự đầu tiên luôn là một chữ số khác ~0~.

Output

• In ra trên một dòng duy nhất: số cách thay thế các dấu "~?~" bằng các chữ số sao cho ~n~ chia hết cho ~2048~. Vì kết quả có thể rất lớn, in phần dư khi lấy kết quả chia cho ~10^9 + 9~

Subtask

• ~20\%~ số test thoả mãn: số dấu "~?~" không quá ~5~.

• ~30\%~ số test khác thoả mãn: số dấu "~?~" không quá ~100~.

• ~50\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

2???

Sample Output 1

1

Note

Ở test ví dụ trên, chỉ có một cách điền duy nhất là ~2048~.