Lộc đang được đào tạo để trở thành một chuyên gia đánh máy hàng đầu cho dự án IUH Coder. Leader của em ấy đã giao một nhiệm vụ về nhà là đánh máy một xâu ký tự in hoa "F", "O" và "X". Lộc đang ăn kem que vào một chiều đông nóng bức và vẫn hy vọng hoàn thành nhiệm vụ này thật nhanh. Em ấy muốn cầm que kem bằng một tay và gõ bằng tay kia. Thật không may, Lộc vẫn còn là một cậu bé mới lớn và mỗi bàn tay của cậu quá nhỏ để có thể chạm hết bàn phím. Em chỉ có thể chạm tới các chữ cái "F" và "X" bằng tay trái và các chữ cái "F" và "O" bằng tay phải.

Xét một xâu ~W~ mà Lộc phải gõ. Lộc có thể bắt đầu gõ bằng bất kỳ tay nào (tay kia cầm que kem). Sau đó, có thể em phải đổi tay nếu cần để gõ các chữ cái theo đúng thứ tự. Gọi ~F(W)~ là số lần tối thiểu Lộc phải đổi tay để gõ một xâu ~W~ như vậy (trong suốt quá trình đó, một tay em luôn cầm que kem và gõ bằng tay còn lại). Ví dụ: nếu ~W = XXFFOOF~ thì Lộc cần phải đổi tay ít nhất ~1~ lần: gõ ~X,X,F,F~ bằng tay trái, rồi đổi tay để gõ ~O,O,F~ bằng tay phải; còn nếu ~W = OOOOO~ thì Lộc không cần đổi tay lần nào cả.

Yêu cầu đặt ra là cho một xâu ~S~ có độ dài ~N~, gọi ~G(S)~ là tổng của ~F(W)~ trên tất cả các xâu con ~W~ của ~S~ (xâu con là một tập con các ký tự liên tiếp của xâu ban đầu). Lưu ý rằng có tất cả ~1+2+...+N = \frac{N(N+1)}{2}~ xâu con như vậy. Hãy giúp Lộc tính giá trị của ~G(S)~ modulo ~10^9+7.~

Input: dòng đầu tiên gồm số ~N~ là độ dài của xâu với ~1 \le N \le 8.10^5~, dòng tiếp theo là xâu cần gõ.

Output: kết quả của bài toán.

Sample input 1:

3

XFO

Sample output 1:

1

Sample input 2:

10

FXXFXFOOXF

Sample output 2:

36

Giải thích:

Ta thấy rằng chuỗi ~XFO~ có các chuỗi con là: ~X, F, O, XF, FO, XFO~ trong đó chỉ có chuỗi cuối mới cần đổi tay để gõ, còn lại hoàn toàn có thể gõ bằng 1 tay.