Cắt và Dán 2

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

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

Ngoài ra có một bộ nhớ tạm $c$ (ban đầu rỗng) và ba loại thao tác:

• Move: dịch con trỏ sang phải một bước, tức là tăng $\ell$ lên $1$.
• Cut: gán $c\leftarrow s_{\text{right}}$, sau đó gán $s\leftarrow s_{\text{left}}$.
• Paste: nối thêm $c$ vào cuối xâu $s$ (thao tác này không làm thay đổi $c$).

Ban đầu $\ell =0$. Ta thực hiện quy trình sau:

1. Thực hiện Move một lần.
2. Thực hiện Cut một lần.
3. Thực hiện Paste đúng $s_{\ell }$ lần.
4. Nếu $\ell =x$ thì dừng, ngược lại quay lại bước 1.

Cho xâu ban đầu $s$ và số nguyên $x$, hãy tính độ 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 trong suốt quá trình 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.
• Mỗi bộ dữ liệu gồm hai dòng: dòng thứ nhất chứa số nguyên $x$, dòng thứ hai chứa xâu $s$.

Dữ liệu ra

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

Ràng buộc

• $1\le t\le 1000$
• $1\le x\le {10}^6$, tổng $x$ trên toàn bộ file dữ liệu không vượt quá ${10}^6$
• $1\le |s|\le 500$, $s$ chỉ gồm các chữ số 1, 2, 3

Ví dụ