Description

Niyiz是个爱玩的小朋友，他今天来到游乐园玩弹弹床。

在他面前，有n个弹弹床排成一排，从1到n编号。弹弹床有两种，标“L”的会向左弹，即弹到编号 小于它的床，而标"R"会向右弹，即弹到编号大于它的床。弹弹床的类型只规定了它的方向，具体弹到哪 是Niyiz自己控制的。

Niyiz可以从任意一个弹弹床开始游戏。他想知道，对于每一个床i ,有多少种方法弹遍所有床，最后在第i个床结束游戏。

答案请对10^9 + 7取模。

Input Format

第一行一个正整数n,表示弹弹床的个数。

第二行一个长度为n、由“L”和"R"构成的字符串s，表示每个弹弹床的类型。

Output Format

一行，n个整数，以空格隔开，表示以每个床结束游戏的方案数对10^9 + 7取模。

Sample

样例输人

3
RRL
6
RLRRRL

样例输出

1 2 1

12 2 4 8 1

Hint

对于30%的数据：1 =< n <= 18 ；

对于另外30%的数据：1 =< n <= 5000,保证s的最后一个字符为R ； 对于100%的数据：1 =< n <= 5000。