Một xâu được gọi là đối xứng nếu như khi đọc chuỗi này từ phải sang trái cũng thu được chuỗi ban đầu. Cho xâu ~𝑆~ độ dài ~𝑁~ chỉ gồm các chữ cái latin in thường.

Yêu cầu: Tìm xâu đối xứng dài nhất gồm các kí tự liên tiếp trong ~S~, kết quả tìm được mod ~10^9~+7.

Input:

• Dòng 1: ~N~ (độ dài của xâu ~S; N<=50 000~)
• Dòng 2: Xâu ký tự độ dài ~N~

Output:

• Một dòng duy nhất gồm độ dài của xâu đối xứng dài nhất (mod ~10^9~+7)

Ví dụ:

input

5
abacd

output

3

*Giới hạn: *

• Có 50% test ứng với ~N<=5000~
• 50% test còn lại ứng với ~N>5000~