Hôm nay trong tiết Tin học, Tài được cô giáo dạy gõ ba ký tự trong tên của mình, chính là “T”, “A”, “I”. Trong \(Q\) ngày tới, mỗi ngày cô giáo sẽ đưa cho Tài một xâu chỉ gồm ba ký tự đã nêu trên để cho Tài luyện gõ phím.

Tài chỉ có thể gõ được hai ký tự “A” và “T” bằng tay trái, hai ký tự “T” và “I” bằng tay phải. Nghĩa là khi bắt đầu làm bài về nhà của một ngày, Tài có thể chọn dùng một trong hai tay để gõ, sau đó trong quá trình làm bài, Tài phải đổi giữa hai tay nếu cần thiết để gõ được hết các ký tự trong xâu theo thứ tự.

Ví dụ: nếu bài về nhà là xâu \(``ATIA"\) thì Tài có thể gõ như sau:

• Đầu tiên Tài sẽ gõ ký tự “A” và “T” bằng tay trái;

• Đổi sang tay phải để gõ ký tự “I”;

• Cuối cùng đổi sang tay trái để gõ nốt ký tự “A”.

Vậy, Tài phải đổi tay 2 lần để gõ hết xâu \(``ATIA"\).

Ký hiệu \(F(S)\) là số lần ít nhất Tài phải đổi tay để gõ hết xâu \(S\).

Hãy xét hai giá trị \(S_{i}\) và \(X_{i}\) lần lượt là xâu ký tự bài về nhà mà cô giáo cho Tài vào ngày thứ \(i\) và câu hỏi mà Tài muốn được giải đáp. \(X_{i}\) có thể là một trong hai giá trị sau:

• Nếu \(X_{i} = 0\) thì Tài muốn biết rằng để hoàn thành bài của ngày thứ \(i\), Tài cần đổi tay ít nhất bao nhiêu lần, hay cụ thể hơn là muốn biết giá trị của \(F(S_{i})\);

• Nếu \(X_{i} = 1\) thì Tài muốn biết rằng nếu phải gõ riêng biệt tất cả các xâu con liên tiếp của \(S_{i}\) thì Tài sẽ phải đổi tay ít nhất bao nhiêu lần. Cụ thể hơn, gọi \(G\) là tập hợp những xâu con liên tiếp của \(S_{i}\) thì Tài muốn tính:

Vì đáp án có thể lớn nên Tài chỉ muốn biết phần dư của kết quả trong phép chia cho \(10^{9} + 7\).

Dữ liệu:

• Dòng đầu gồm một số nguyên \(Q\ (1 \leq Q \leq 100)\) là số ngày Tài phải làm bài tập;

• \(Q\) dòng tiếp theo, mỗi dòng gồm một số nguyên \(X_{i}\) \(\left( 0 \leq X_{i} \leq 1 \right)\) và một xâu \(S_{i}\) \((1 \leq\) Độ dài xâu \(S_{i}\) \(\leq 10^{5})\). Tổng độ dài các xâu \(S_{i}\) trong tất cả \(Q\) ngày không vượt quá \(4 \times 10^{6}\).

Kết quả:

+ Ghi \(Q\) dòng, dòng thứ \(i\ (1 \leq i \leq Q)\) là đáp án cho câu hỏi mà Tài muốn được giải đáp vào ngày thứ \(i\).

Ví dụ:

Chú ý:

• Subtask 1 (40% số điểm): \(X_{i} = 0\ (1 \leq i \leq Q)\);

• Subtask 2 (40% số điểm): Bài tập về nhà của Tài không có ký tự “T”;

• Subtask 3 (20% số điểm): Không có ràng buộc bổ sung.