Sau bao nỗ lực vượt qua hang động sấm sét, cơn bão bên ngoài cũng dần tan biến, để lộ ra trước mắt Ash một khung cảnh hùng vĩ đến choáng ngợp: một cánh cổng đá nguyên khối khổng lồ, cao sừng sững chạm đến những đám mây, toàn bộ bề mặt bị che phủ bởi những lớp rễ cây cổ thụ chằng chịt hàng ngàn năm tuổi. Linh cảm mách bảo cậu rằng đây chính là Ruins of Alph huyền thoại, một khu bảo tồn thiêng liêng lưu giữ những bí mật nguyên thủy nhất về sự hình thành và khởi nguyên của toàn bộ thế giới Pokemon. Khi Pikachu tò mò tiến lại gần và cọ má vào bề mặt cánh cổng để làm sạch lớp bụi rêu, hàng loạt những ký tự kỳ lạ được khắc sâu trên đá bỗng nhiên tỏa ra thứ ánh sáng xanh ngọc bích mờ ảo. Trong chớp mắt, những ký tự đó tách rời khỏi vách đá, hóa thành những sinh vật sống bay lượn vòng quanh không trung. Đó chính là những Pokemon Unown vô cùng hiếm gặp - những sinh vật không gian có hình dạng trùng khớp hoàn hảo với các chữ cái Latinh trong bảng chữ cái con người. Khi Ash vươn tay chạm nhẹ vào phần trung tâm của cánh cổng, các Unown lập tức hội tụ lại, xếp nối đuôi nhau thành một chuỗi ký tự \(S\) dài dằng dặc, chỉ bao gồm toàn các chữ cái tiếng Anh in thường, uốn lượn như một con rồng ánh sáng. Đột nhiên, một giọng nói trầm mặc, vang vọng từ cõi hư vô truyền thẳng vào tâm trí cậu, mang theo uy nghiêm của những bậc cổ nhân: "Hỡi kẻ lữ hành mang trái tim thuần khiết, để phá vỡ phong ấn và mở được cánh cổng của những người sáng thế, ngươi buộc phải thấu hiểu trọn vẹn sự 'Hài hòa' của ngôn ngữ vũ trụ này".

Nhớ lại những buổi chiều ngồi học ngoan ngoãn tại phòng nghiên cứu, Professor Oak đã từng say sưa giảng giải rằng, "Độ hài hòa" của một chuỗi văn bản cổ đại được định nghĩa một cách vô cùng khắt khe: đó chính là tổng số lượng các cặp \((A, B)\) thỏa mãn đồng thời hai điều kiện tiên quyết:

• Thứ nhất, \(A\) và \(B\) phải là hai xâu con (bao gồm các ký tự đứng liền kề nhau) hoàn toàn không giao nhau hay chồng lấn lên nhau của chuỗi gốc \(S\); nói một cách chính xác về mặt toán học, vị trí ký tự kết thúc của đoạn \(A\) bắt buộc phải nằm trước vị trí ký tự bắt đầu của đoạn \(B\) để không gây ra những nghịch lý về không thời gian.
• Thứ hai, và cũng là điều kiện khó nhằn nhất, cả đoạn văn bản \(A\) và đoạn văn bản \(B\) đều phải mang cấu trúc của một xâu đối xứng (Palindrome - nghĩa là dù ngươi có đọc từ trái sang phải hay đọc ngược từ phải sang trái thì ý nghĩa và âm điệu của chúng vẫn hoàn toàn giống hệt nhau), đại diện cho sự cân bằng âm dương tuyệt đối của vạn vật trong vũ trụ bao la.

Vì chuỗi ký tự phát sáng trên cánh cổng quá dài, bao gồm hàng vạn ký tự liên tiếp nhau, Ash hoàn toàn rơi vào trạng thái tuyệt vọng nếu phải đếm nhẩm bằng đầu óc con người. Cậu thừa hiểu rằng, nếu đưa ra một con số sai lệch dù chỉ một đơn vị, hệ thống phòng thủ quang học của di tích sẽ lập tức kích hoạt và biến cậu thành tro bụi. Thời gian không còn nhiều, hãy thể hiện tài năng lập trình xuất chúng của bạn để viết ra một chương trình thuật toán đếm chính xác số lượng cặp xâu con thỏa mãn hai điều kiện khắc nghiệt kia. Do số lượng kết quả đếm được có thể vượt qua giới hạn lưu trữ của các kiểu dữ liệu thông thường, hãy bảo vệ an toàn cho kết quả bằng cách in ra phần dư của nó khi chia cho một hằng số nguyên tố lớn là \(10^9 + 7\).

Input

• Một dòng duy nhất chứa xâu \(S\) (\(1 \le |S| \le 10^5\)) gồm các chữ cái tiếng Anh in thường (từ a đến z) tượng trưng cho chuỗi ngôn ngữ Unown phát sáng.

Output

• In ra một số nguyên duy nhất là phần dư của tổng số lượng cặp \((A, B)\) thỏa mãn điều kiện hài hòa khi chia cho \(10^9 + 7\).

Example

aba

3

aaaa

15

pokemon

21

Scoring

• Subtask \(1\) (\(30\%\) điểm): \(|S| \le 100\).
• Subtask \(2\) (\(30\%\) điểm): \(|S| \le 2000\).
• Subtask \(3\) (\(40\%\) điểm): Không còn ràng buộc gì thêm.