Huy đang tạo bài tập cho kỳ thi sắp tới thì bàn phím bị hỏng, khiến cho khi một phím bị nhấn thì một số ký tự liên tiếp sẽ được tạo ra thay vì chỉ một. Ví dụ, Huy muốn gõ xâu "typing", nhưng vì bàn phím bị hỏng dẫn đến kết quả là tạo ra xâu bị lỗi "tyypppinng". Huy muốn tìm lại xâu ban đầu từ xâu bị lỗi, nhưng Huy nhận ra là có rất nhiều xâu như vậy. Ví dụ như xâu "typing " và "tyyping" đều có thể tạo ra xâu lỗi là "tyypppinng", nhưng xâu "typiing" không tạo ra xâu lỗi là "tyypppinng". Cho xâu bị lỗi, bạn hãy giúp Huy tìm số lượng xâu mà có thể tạo nên xâu bị lỗi đó.

Input

Gồm một dòng duy nhất chứa xâu S chỉ gồm các ký tự là chữa cái in thường là xâu bị lỗi ( | S | ≤ ~ 10^5 ~).

Output

Gồm một dòng là số lượng xâu mà có thể tạo nên xâu bị lỗi S. Vì kết quả có thể rất lớn nên bạnhãy in kết quả theo phần dư của 1000000007.

Sample

Input #1

tyypppinng

Output #1

12

Problem source: Beginner Free Contest 31