Chia xâu số thành các nhóm không giảm

Cho một xâu \(s\) khác rỗng chỉ gồm các chữ số. Ta cắt xâu thành một số nhóm liên tiếp (mỗi chữ số thuộc đúng một nhóm, giữ nguyên thứ tự) sao cho tổng các chữ số của mỗi nhóm không vượt quá tổng các chữ số của nhóm ngay bên phải nó, tức là dãy tổng các nhóm là không giảm từ trái sang phải. Việc không cắt gì (cả xâu là một nhóm) cũng được tính là một cách chia hợp lệ.

Ví dụ với \(s = 635\): chia thành \([635]\) (tổng \(14\)) hoặc \([6][35]\) (tổng \(6 \le 8\)) là hợp lệ, còn \([63][5]\) (tổng \(9 > 5\)) và \([6][3][5]\) (tổng \(6 > 3\)) thì không. Vậy có \(2\) cách.

Hãy đếm số cách chia hợp lệ của mỗi xâu. Hai cách khác nhau nếu tập vị trí cắt khác nhau. Vì kết quả có thể rất lớn, in ra phần dư khi chia cho \(10^9 + 7\).

Input

Dữ liệu gồm nhiều bộ test, mỗi bộ test là một xâu trên một dòng. Kết thúc bằng một dòng chứa đúng từ bye (dòng này không phải bộ test).

Output

Với bộ test thứ \(k\) (đánh số từ 1), in ra một dòng có dạng k. n, trong đó \(n\) là số cách chia hợp lệ lấy modulo \(10^9 + 7\).

Constraints

• Số bộ test không quá \(20\).
• Mỗi xâu có độ dài từ \(1\) đến \(200\) và chỉ gồm các chữ số thập phân.

Sample Input

2213
1234
5
40
bye

Sample Output

1. 5
2. 6
3. 1
4. 1

Explanation

Xâu 2213 có \(5\) cách: \([2213]\), \([2][213]\), \([22][13]\), \([2][2][13]\), \([2][21][3]\). Xâu 5 chỉ có \(1\) cách. Xâu 40: cách \([4][0]\) không hợp lệ vì \(4 > 0\) nên chỉ còn cách giữ nguyên cả xâu, được \(1\) cách.