Chưng là một người đam mê su kem và cậu ấy đã tạo nên những chiếc su siêu ngon lành cho Quýt. Chưng đã sáng tạo ra ~26~ hương vị su kem khác nhau được kí hiệu là các chữ cái viết thường (~a-z~).

Một hôm nọ Chưng đã nấu thành công n chiếc bánh khác nhau và chuẩn bị đem qua nhà Quýt. Nhưng đối với Chưng thì bánh không chỉ ngon mà còn phải đẹp vì vậy cậu ấy đã quyết định ghép các su kem liên tiếp lại với nhau thành một su kem đối xứng.

Biết rằng su kem đối xứng là chuỗi các bánh liên tiếp với độ dài chẵn và ký hiệu hương vị của từng bánh khi ghép lại sẽ tạo thành 1 xâu đối xứng. Ngoài ra còn có một cách khác để tạo nên một su kem đối xứng là xu kem đó phải được ghép lại từ nhiều su kem đối xứng liên tiếp với kích thước nhỏ hơn.

VD: ~aa~, ~aabaab~ là những su kem đối xứng còn ~quyt~, ~chung~ thì không.

Vì lỡ nấu quá nhiều bánh nên Chưng không biết chọn ra một su kem đối xứng nào tặng cho Quýt. Bạn hãy giúp cậu ấy đếm xem có bao nhiêu cách tạo nên su kem đối xứng với n chiếc bánh có sẵn

Input

• Dòng đầu tiên gồm một số nguyên ~N~ với ~1 \le N \le 5.10^5~. Số lượng bánh su kem ban đầu được đánh số từ ~1~ đên ~n.~

• Dòng tiếp theo chứa ~n~ chữ cái trong đó chữ cái thứ ~i~ sẽ thuộc một trong 26 chữ cái tiếng Anh viết thường. Đại diện cho hương vị của từng chiếc bánh.

Output

Một dòng duy nhất là số cách tạo nên các su kem đối xứng từ các chiếc bánh đã cho.

Sample Input 1

6
abaaba

Sample Output 1

3

Giải thích:

Ta sẽ có các su kem đối xứng là: ~aa~, ~baab~ và ~abaaba~.