Cho một xâu \(S\) chỉ gồm các chữ cái Latin in thường có thể được mã hóa sang xâu \(T\) chỉ gồm các chữ số bằng cách thay từng chữ cái trong xâu \(S\) bằng thứ tự của nó trong bảng chữ cái tiếng Anh ('a' \(\rightarrow 1\), 'b' \(\rightarrow 2\), 'c' \(\rightarrow 3\), ...). Cho trước xâu \(T\) chỉ gồm chữ số, hãy đếm xem có bao nhiêu cách để giải mã xâu \(T\) thành xâu \(S\).
Vì kết quả có thể rất lớn, hãy in ra dư của kết quả khi chia cho \(10^9+7\)

Input

• Dòng đầu tiên gồm xâu \(T\) chỉ gồm chữ số.
• \(\vert{}T\vert{} \le 10^5\)

Output

• Số cách để giải mã xâu \(T\).

Example

226

3