Cây tre ngàn đốt

Xem dạng PDF

Gửi bài giải

Điểm: 1,60 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

To read the problem statement in English, choose the language using the flag on the navigation bar.

Dựa trên câu truyện dân gian Việt Nam "Cây tre trăm đốt"

Ngày xửa ngày xưa, ở một ngôi làng nọ, có một phú ông giàu có. Phú ông có một cô con gái hiền lành, nết na. Trong ngôi làng, cũng có tiều phu, rất cần cù chịu khó. Thấy anh tiều phu rất siêng năng, phú ông rất muốn thuê anh tiều phu. Phú ông hứa: "Con chịu khó làm lụng giúp ta, ba năm nữa ta sẽ gả con gái ta cho". Tin lời phú ông, anh tiều phu vất vả ngày đêm lên rừng kiếm thật nhiều củi. Sau ba năm, phú ông đã giàu lên một phần là nhờ công sức cực nhọc của anh tiều phu. Tuy vậy, phú ông lại trở mặt, không muốn gả con gái cho anh tiều phu. Để gây khó khăn cho anh tiều phu, phú ông thách thức anh tiều phu, cần phải lên rừng kiếm cây tre ngàn đốt về để xây nhà thì ông mới gả con gái cho. Thật thà tin lời phú ông, anh tiều phu nhanh chóng lên rừng tìm cây tre. Nhưng tìm mãi không thấy, nên anh tiều phu buồn tủi, ngồi vào bờ tre và khóc. Lúc đó ông Bụt hiện lên, hỏi han anh tiều phu. Sau khi nghe anh tiều phu giải thích, ông Bụt bảo anh tiều phu đốn tre sao cho tổng cộng đủ một ngàn dốt và đem về đây. Sau đó, ông Bụt dạy anh tiều phu câu thần chú "Khắc nhập, khắc nhập", và toàn bộ cây tre mà anh tiều phu đã đốn gộp lại thành một.

Sự việc diễn ra ở xứ sở VNOI, nên mỗi đốt của của cây tre đều có một kí tự tiếng Anh in thường, do đó mỗi một cây tre có thể được biểu diễn bởi một xâu kí tự, với kí tự đầu tiên là kí tự ở đốt gốc và kí tự cuối cùng là kí tự của đốt ngọn. Câu thần chú của "Khắc nhập, khắc nhập" cũng là câu thần chú đặc biệt: các cây tre sẽ được nối lại thành một cây tre có thứ tự từ điển nhỏ nhất!

image

Minh họa cho câu thần chú "Khắc nhập, khắc nhập" cho 4 cây tre biểu diễn bởi các xâu tre, is, a, longtree. Câu thần chú nối các cây tre lại thành cây biểu diễn bởi xâu aislongtreetre và đây là cây có xâu biểu diễn có thứ tự từ điển nhỏ nhất.

Nhưng mang một cây tre một ngàn đốt từ rừng về làng quả là vất vả. Do đó ông Bụt dạy anh tiều phu thêm một câu thần chú nữa là "Khắc xuất, khắc xuất". Sau khi đọc câu thần chú này, cây tre một trăm đốt này sẽ bị cắt thành một vài cây tre nhỏ hơn. Như vậy anh tiều phu có thể mang các cây tre này về làng dễ hơn, rồi sử dụng câu thần chú "Khắc nhập, khắc nhập" để lại tạo ra cây tre ngàn đốt.

image

Minh họa cho câu thần chú "Khắc xuất, khắc xuất" cho cây tre biểu diễn bởi xâu aislongtreetre thành các cây tre biểu diễn bởi xâu aisl, ongtreetre. Lưu ý đây không phải là cách duy nhât sử dụng câu thần chú này để chia cắt cây tre.

Để qua được con mắt tinh tường của phú ông, anh tiều phu cần đảm bảo rằng, nếu như gọi câu thần chú "Khắc xuất, khác xuất", sau đó lại gọi "Khắc nhập, khắc nhập", xâu kí tự của cây tre ngàn đốt mới không đổi so với cây tre ngàn đốt cũ. Nếu hai cây tre khác nhau, phú ông có thể dễ dàng phát hiện đây là những cây tre đã bị cắt và nối lại. May mắn thay, với câu thần chú "Khắc xuất, khắc xuất", anh tiều phu có thể chọn vị trí cắt các cây tre.

Cho xâu kí tự ~S~ là xâu kí tự biểu diễn cây tre ngàn đốt (độ dài của ~S~ không nhất thiết phải là ~1000~, vì ngàn là tên gọi). Hãy đếm số cách sử dụng câu thần chú "Khắc xuất, khắc xuất" để cắt cây tre này, sau đó lại gọi câu thần chú "Khắc nhập, khắc nhập", thu được cây tre vẫn mà có thể biểu diễn bởi xâu kí tự ~S~. Vì đáp án có thể rất lớn, nên thay vào đó, hãy in ra số dư của đáp án khi chia ~10^9 + 7~.

Hai cách sử dụng câu thần chú "Khắc xuất, khắc xuất" là khác nhau, nếu như vị trí cắt cây tre ngàn đốt để tạo ra các cây tre nhỏ hơn là khác nhau.

Một xâu kí tự ~a~ được gọi là có thứ tự từ điển nhỏ hơn xâu kí tự ~b~ nếu một trong các điều sau thỏa mãn:

  • ~a~ là tiền tố của ~b~, nhưng ~a \ne b~.

  • tại vị trí đầu tiên mà xâu ~a~ và ~b~ khác nhau, xâu ~a~ có kí tự xuất hiện trước kí tự tương ứng ở xâu ~b~ trong bảng chữ cái tiếng Anh.

Input

Mỗi một test gồm nhiều test case khác nhau. Dòng đầu tiên của một test chứa số nguyên ~t~ (~t \le 2000~) là số lượng test case. Các test case được mô tả như sau.

Dòng đầu tiên và duy nhất của mỗi test case chứa xâu ~S~ (~1 \le |S| \le 2000~, ~S~ chỉ chứa các kí tự tiếng Anh in thường) là xâu biểu diễn của cây tre mà anh tiều phu cần phải mang về làng.

Dữ liệu đảm bảo tổng độ dài các cây tre của tất cả các test case trong một test không quá ~2000~.

Output

Với mỗi test case, hãy tìm số lượng cách sử dụng câu thần chú "Khắc xuất, khắc xuất" để cắt cây tre thành các cây tre bé hơn, sao cho sau khi gọi câu thần chú "Khắc nhập, khắc nhập", ta thu được cây tre được nối lại mà xâu biểu diễn của nó cũng là xâu ~S~. Vì đáp án có thể rất lớn, nên thay vào đó, hãy in ra số dư của đáp án khi chia ~10^9 + 7~.

Scoring

  • Subtask 1, ứng với ~25~ điểm, các cây tre đã cho có độ dài không quá ~5~.

  • Subtask 2, ứng với ~100~ điểm, tổng độ dài của các cây tre không quá ~100~.

  • Subtask 3, ứng với ~234~ điểm, không có ràng buộc gì thêm.

Tổng cộng bài toán này có ~359~ điểm.

Sample Input 1

3
a
acb
ababa

Sample Output 1

0
2
3

Notes

Trong test case đầu tiên, cây tre đã cho được biểu diễn bởi xâu a. Cây tre này gồm có một đốt, nên không thể chia cây tre này thành các cây tre nhỏ hơn.

Trong test case thứ hai, cây tre đã cho được biểu diễn bởi xâu acb. Ta có hai cách gọi câu thần chú "Khắc xuất, khắc xuất" để chia cây tre như sau:

  • Chia thành hai cây tre có biểu diễn là acb,

  • Chia thành hai cây tre có biểu diễn là acb.

Ta không thể chia cây tre acb thành ba cây tre một đốt a, cb, vì nếu chia như vậy, sau khi gọi câu thần chú "Khắc nhập, khắc nhập", cây tre thu được có biểu diễn là abc, khác với cây tre đã cho.

Trong test case thứ ba, cây tre đã cho được biểu diễn bởi xâu ababab. Ta có các cách sử dụng câu thần chú "Khắc xuất, khắc xuất" để chia cây tre như sau:

  • a|baba,

  • aba|ba,

  • a|ba|ba.


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.