cxlove is a good man

Time Limit: 6000/3000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

众所周知,爱酱(cxlove)是个绝世好男人。好男人的标准之一就是能解决妹子提出的一切问题!

有一天,好奇宝宝娜娜做题时发现了一种神器的树。树的前几层如下图:
如你所见:

除开最上面两个奇怪的东西之外,树的每个节点上都有一个数字,某个节点的分子是在该节点左上的第一个节点和其右上节点的分子的和,某个节点的分母是在该节点的左上的第一个节点和其右上第一个节点的分母的和。

例如,2/3 这个节点的左上第一个节点是1/2,右上第一个节点是 1/1

现在给定从根节点到某个节点的路径。用L(x), R(x)表示。L(x)表示像沿着左子树走了 步,R(x)表示沿着右走了 x 步。

例如:L(2)R(1)L(1) 表示3/8
 

Input

一个数字n

接下来 行,每行一个字母a,一个数字b

a='L' 表示沿着树往左走

a='R' 表示沿着树往右走

n ≤ 10^7

所有 的和小于10^18

Output

两个数 p, q, 分别是到达节点的分子mod 1000000007  和分母mod 1000000007

Sample Input

1
R 5
3
R 2
R 5
R 3

Sample Output

6/1
11/1

Source

v_o_f

Manager

Information
Solved Number5
Submit Number17
Problem Tags
implementation
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel