Cuộc chiến vi khuẩn

Một ống nghiệm nằm ngang được chia thành $n$ ô liên tiếp, đánh số từ $1$ đến $n$. Mỗi ô chứa đúng một khuẩn lạc thuộc một loại vi khuẩn nào đó, mỗi loại được ký hiệu bằng một chữ cái Latin thường từ a đến z. Như vậy trạng thái của ống nghiệm tại mỗi thời điểm được mô tả bởi một xâu gồm $n$ chữ cái thường.

Thỉnh thoảng một khuẩn lạc có thể thôn tính một khuẩn lạc ở ô kề bên (bên trái hoặc bên phải, và phải nằm trong phạm vi ống nghiệm). Khi đó khuẩn lạc bị tấn công lập tức bị tiêu diệt và được thay bằng một khuẩn lạc cùng loại với kẻ tấn công, còn kẻ tấn công giữ nguyên loại của mình. Tại mỗi thời điểm chỉ có nhiều nhất một cuộc tấn công xảy ra.

Ví dụ với trạng thái ban đầu là babb, cuộc tấn công tiếp theo có $6$ khả năng: ô $1$ tấn công ô $2$ cho ra bbbb; ô $2$ tấn công ô $1$ cho ra aabb; ô $2$ tấn công ô $3$ cho ra baab; ô $3$ tấn công ô $2$ cho ra bbbb; còn ô $3$ tấn công ô $4$ hoặc ô $4$ tấn công ô $3$ đều không làm trạng thái thay đổi.

Cho trạng thái ban đầu của ống nghiệm, hãy đếm số trạng thái khác nhau có thể thu được sau một dãy tấn công bất kỳ. Dãy tấn công có thể rỗng, nên trạng thái ban đầu cũng được tính. Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $n$: số ô của ống nghiệm.
• Dòng thứ hai chứa xâu $s$ gồm $n$ chữ cái Latin thường, mô tả trạng thái ban đầu.

Dữ liệu ra

Một số nguyên duy nhất: số trạng thái khác nhau có thể thu được, lấy phần dư khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le n\le 5000$
• $s$ chỉ gồm các chữ cái Latin thường từ a đến z

Ví dụ