URI Online Judge | 2793

HM

By Lucas Maciel BR Brazil

Timelimit: 1

"Men & Women" is a clothing store in Montes Claros that Isabel leads. This store is very famous for having exactly the same number of men's and women's clothing. Very organized, Isabel wants to categorize her stock of clothes keeping the order in which they are stored.

Order in which clothes are stored. In this example we have MFFMFMFFMFMM where F denotes women's clothing and M men's clothing.

Isabel still does not know how many categories she will need. She only decided two criteria:

  1. All categories will have the same number of men's and women's clothing.
  2. The clothes are already hanging on a large hanger, and to minimize her work, she just wants to place divisions between the categories, without changing any local clothes.

In the example of the figure, if Isabel uses 2 categories, she can either put the first four clothes in one category and the other eight in the second, put the first six clothes in one category and the last six in the second. Isabel may also prefer to use a category only (encompassing all clothing) or use 3 different categories (separating the clothes in MFFM, FM, FFMFMM), but note that it is not possible to separate into four or more categories keeping the same number of men's clothing and feminine in each.

Help Isabel then define how many ways she can categorize her inventory without violating the company's tradition.

Input

The entry contains only one line with a sequence of letters indicating the type of clothing in Isabel's shop: M indicates a masculine clothing and F feminine clothing.

The entrance will contain between \(2\) and \(10^7\) clothes, and will always have the same number of men's and women's clothing.

Output

Write in the output just one line containing an integer: the number of possible ways Isabel can categorize her stock.

Since the answer can be very large, write the its remainder by \(10^9+7\).

Input Sample Output Sample

MFMF

2

MFMFFM

4

MMFF

1