Alice cần tạo một mật khẩu mạnh cho tài khoản mạng xã hội của cô. Cô muốn viết một chương trình tự động, chương trình này nhận vào một xâu ký tự \(S\) chỉ gồm các chữ số và chữ cái trong bảng chữ cái tiếng Anh và trả ra một xâu ký tự \(T\) là mật khẩu được tạo. Xâu \(T\) được tạo từ xâu \(S\) theo quy tắc sau đây:

• Ký tự đầu tiên của xâu \(T\) là ký tự cuối cùng của xâu \(S\).
• Tiếp theo là tổng các ký tự số trong xâu \(S\).
• Tiếp theo là các ký tự số trong xâu \(S\) được sắp xếp theo thứ tự tăng dần.
• Tiếp theo là các ký tự chữ trong xâu \(S\) theo đúng thứ tự xuất hiện trong \(S\). Nếu ký tự là chữ hoa, chuyển sang chữ thường tương ứng.
• Cuối cùng là số lượng ký tự là chữ hoa trong xâu \(S\).

Sau khi tạo được xâu \(T\), Alice tự hỏi rằng có bao nhiêu xâu \(S\) khác nhau có thể tạo ra xâu \(T\) như vậy. Bạn hãy trả lời câu hỏi này giúp Alice nhé.

Input

• Một dòng duy nhất gồm một xâu \(T\). Dữ liệu đầu vào đảm bảo xâu \(T\) được tạo thành từ ít nhất một xâu \(S\) có không quá \(10^5\) ký tự.

Output

• Một dòng duy nhất là số xâu \(S\) có thể tạo thành xâu \(T\). Vì kết quả có thể rất lớn nên chỉ cần in phần dư của nó khi chia cho \(10^9 + 7\).

Example

C422ac1

3

Scoring

• 30% số điểm có xâu \(S\) ban đầu chỉ bao gồm các chữ cái in thường và tối đa 1 ký tự số.
• 30% số điểm khác có xâu \(S\) ban đầu chỉ bao gồm các chữ cái in thường và tối đa 2 ký tự số.
• 20% số điểm khác có xâu \(S\) ban đầu có tối đa 1 ký tự số.
• 20% số điểm còn lại không có giới hạn gì thêm.