Xét xâu S độ dài không vượt quá 1018 chỉ gồm các ký tự ‘a’ đến ’z’ được mã hoá thành xâu SE (chỉ gồm các ký tự ‘a’ đến ‘z’ và ký tự ‘0’ đến ‘9’) như sau: Đi từ trái qua phải, mã hoá dãy các ký tự liên tiếp bằng nhau trong S thành ký tự đại diện và số lượng. Độ dài các xâu mã hoá không vượt quá 1000.
Ví dụ, xâu S=aaabbbbaaaaaaaaaaz thì SE=a3b4a10z1
Yêu cầu: Cho xâu S được mã hoá thành SE, đếm số lượng xâu khác nhau nhận được từ S bằng cách giữ nguyên hoặc xoá đi một số ký tự (đưa ra kết quả mod 111539786)
Ví dụ: SE=a10 thì số lượng các xâu khác nhau nhận được từ S là 10
Input
- Dòng đầu chứa số T là số bộ dữ liệu (T<=1000);
- T dòng sau, mỗi dòng chứa xâu SE là mã hóa của S.
Output
- Gồm T dòng, mỗi dòng là kết quả tương ứng với dữ liệu vào.
Ví dụ về vào ra dữ liệu
Input
2
a10
b1a1b1
Output
10
6
Nguồn: 3D 20152016