So khớp DNA

Với hai xâu $s$ và $t$ cùng độ dài $n$, đặt $h(s,t)$ là số vị trí mà hai xâu có cùng ký tự.

Ký hiệu $s^{(i)}$ là xâu thu được từ $s$ sau $i$ lần dịch vòng sang trái. Khoảng cách Vasya giữa hai xâu độ dài $n$ được định nghĩa là

$$\rho (s,t)=\sum _{i=0}^{n-1}\sum _{j=0}^{n-1}h(s^{(i)},t^{(j)}).$$

Chẳng hạn với $s=$ AGC và $t=$ CGT:

$$\rho (\text{AGC},\text{CGT})=1+1+0+0+1+1+1+0+1=6.$$

Cho xâu $s$ độ dài $n$ chỉ gồm các ký tự A, C, G, T. Hãy đếm số xâu $t$ độ dài $n$ cũng chỉ gồm các ký tự A, C, G, T sao cho $\rho (s,t)$ đạt giá trị lớn nhất có thể. Hai xâu $t_1\ne t_2$ được tính là hai xâu khác nhau ngay cả khi xâu này là một phép dịch vòng của xâu kia.

Kết quả có thể rất lớn, hãy in ra phần dư khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là độ dài xâu.
• Dòng thứ hai chứa xâu $s$ độ dài $n$ gồm các ký tự A, C, G, T.

Dữ liệu ra

Một số nguyên duy nhất: số xâu $t$ làm $\rho (s,t)$ đạt giá trị lớn nhất, lấy phần dư cho ${10}^9+7$.

Ràng buộc

• $1\le n\le {10}^5$
• $s$ chỉ gồm các ký tự A, C, G, T

Ví dụ