Description

Alice和Bob在用n张牌玩一个游戏,这n张牌的编号为1到n,在游戏的一开始,每张牌

会被随机地分配给Alice或Bob.

这个游戏由若干回合组成,在每一回合,我们会随机选两张不相同的牌x和y.然后编号大

的牌将会被拿给编号小的牌的主人.

举个例子,如果Alice拥有编号为1的牌,而Bob拥有编号为2的牌,并且我们在当前回合

随机到的数为1和2,那么2将会被拿给Alice.

有一个叫Carol的人观看了游戏的全过程.在整个游戏开始前,Carol钦点了一个状态,并

且说,如果在游戏开始时,或者在任一回合结束时,当前牌的分布和他钦点的状态是一致的,那

么他就会吃一颗豆子.

如果在某一回合结束后,所有牌都属于同一个人,那么游戏将结束.

不妨假设Carol要吃的豆子数的期望为p/q,Carol感兴趣的是满足x·q≡p(mod10^9+7)

的x.请你输出x.

Format

Input

第一行为一个整数n,表示牌的数量.

接下来为一个长度为n的字符串,表示Carol钦点的状态.其中第i个字符为A,表示在

Carol钦点的状态中,第i张牌要属于Alice,为B则表示这张牌要属于Bob.

1≤n≤10^5

Output

输出一行一个整数,表示答案

Samples

3
BAB

375000003