Bờm là một tay sai hữu hiệu của Phú ông. Hôm trước, Bờm đã giúp phú ông tìm được một rương vàng ở trên núi nên Phú ông muốn dành cho Bờm một phần thưởng mà Bờm rất thích đó là xôi. Nhưng lấy được phần thưởng của Phú ông đâu dễ. Phú ông đưa cho bờm một xâu \(S\) và bảo Bờm hãy tìm xâu đối xứng bằng cách giữ nguyên hoặc xóa đi một số kí tự để phần còn là một xâu đối xứng. Một xâu được gọi là xâu đối xứng nếu đọc từ trái qua phải cũng giống như đọc từ phải qua trái và hai cách xóa được gọi là khác nhau nếu tồn tại một vị trí mà trong cách này thì xóa còn trong cách kia thì không xóa (xâu rỗng cũng được tính là một cách). Số cách xóa xâu mà Bờm tìm được chính là số nắm xôi mà Bờm nhận được từ Phú ông, mỗi cách xóa được một nắm xôi. Bờm vốn là người rất tham ăn nên muốn tìm được tất cả các cách xóa để nhận được nhiều xôi nhưng chán nỗi Bờm lại không biết làm thế nào. Bờm muốn nhờ các nhà lập trình tài ba giúp Bờm tìm được nhiều cách xóa nhất và nhanh nhất.

Yêu cầu: Tìm số nắm xôi nhiều nhất mà Bờm có thể nhận được từ Phú ông?

Input

• Dòng đầu chứa số nguyên dương \(M (M \leq 10^9)\)
• Tiếp theo là một số dòng, mỗi dòng chứa một xâu kí tự chỉ gồm các kí tự từ \('a'\) đến \('z'\) mô tả một bộ dữ liệu

Output

• Gồm một số dòng, mỗi dòng là đáp án của bộ dữ liệu tương ứng với file dữ liệu vào chia dư cho \(M\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): độ dài xâu \(< 15\).
• Subtask \(2\) (\(75\%\) số điểm): độ dài xâu \(< 200\).

Example

100 
a 
ab 

2 
3