Cắt, Dán và Độ dài

Ta có một xâu $s$ chỉ gồm các chữ số $1$, $2$, $3$. Độ dài của $s$ ký hiệu là $|s|$, và ký tự thứ $i$ (tính từ $1$) ký hiệu là $s_i$.

Có một con trỏ với vị trí $\ell \in \{0,1,\dots ,|s|\}$: khi $\ell =0$ con trỏ đứng trước ký tự đầu tiên, khi $\ell =|s|$ con trỏ đứng sau ký tự cuối cùng, còn khi $0<\ell <|s|$ con trỏ nằm giữa $s_{\ell }$ và $s_{\ell +1}$. Gọi $s_{\text{trái}}$ là phần xâu bên trái con trỏ và $s_{\text{phải}}$ là phần xâu bên phải con trỏ.

Ta còn có một bộ nhớ đệm $c$, ban đầu rỗng. Có ba thao tác:

• Di chuyển: dịch con trỏ sang phải một bước, tức tăng $\ell$ lên $1$.
• Cắt: gán $c\leftarrow s_{\text{phải}}$, rồi gán $s\leftarrow s_{\text{trái}}$.
• Dán: nối thêm giá trị của $c$ vào cuối xâu $s$ (thao tác này không làm thay đổi $c$).

Con trỏ bắt đầu tại $\ell =0$. Sau đó ta lặp lại quy trình sau:

1. Thực hiện thao tác Di chuyển một lần.
2. Thực hiện thao tác Cắt một lần.
3. Thực hiện thao tác Dán đúng $s_{\ell }$ lần.
4. Nếu $\ell =x$ thì dừng; ngược lại quay về bước 1.

Cho xâu ban đầu $s$ và số nguyên $x$, hãy tìm độ dài của $s$ khi quy trình dừng lại. Vì giá trị này có thể rất lớn, chỉ cần in ra phần dư khi chia cho ${10}^9+7$.

Dữ liệu đảm bảo rằng tại mọi thời điểm luôn có $\ell \le |s|$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$: số lượng bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng thứ nhất chứa số nguyên $x$.
  • Dòng thứ hai chứa xâu ban đầu $s$ (chỉ gồm các chữ số $1$, $2$, $3$).

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa độ dài của $s$ khi quy trình dừng, lấy phần dư khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le t\le 1000$
• $1\le x\le {10}^6$
• $1\le |s|\le 500$
• Tổng của $x$ trên toàn bộ tệp không vượt quá ${10}^6$.

Ví dụ