Hofstader

A sequência de Hofstader Figure-Figure $R_n, S_n$, para um $n$ natural, é dada por $$\begin{array}{l} R_1 = 1 \\ S_1 = 2 \\ R_n = R_{n - 1} + S_{n - 1}, n > 1\\ \end{array}$$ onde $S_n$ é a sequência crescente dos positivos não presentes na sequência $R_n$. Os primeiros termos de $S_n$ são 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, $\ldots$ Observe que $R_n$ não tem termos consecutivos, isto é, $R_{n + 1} - R_n > 1, \forall n\in\mathbb{N}$.

Dado o valor de $n$ determine o valor de $R_n$ ou $S_n$, conforme for indicado. Como este valor pode ser muito grande, imprima o resto de sua divisão por $10^9 + 7$.

Entrada

A entrada é representada por uma única linha contendo os valores de $I$ e $n$ $(I\in \lbrace R, S\rbrace$, $1\leq n\leq 10^6)$, separados por um espaço em branco, onde $I$ é o identificador da sequência a ser computada ($R$ ou $S$) e $n$ é a posição do termo na sequência.

Saída

Imprima, em uma linha, o resto da divisão do valor do $n$-ésimo termo da sequência indicada por $10^9 + 7$.

Exemplo de entrada 1

R 2

Exemplo de saída 1

3

Explicação do exemplo 1: No primeiro caso, $R_2 = R_1 + S_1 = 1 + 2 = 3$.

Exemplo de entrada 2

S 3

Exemplo de saída 2

5

Exemplo de entrada 3

S 10

Exemplo de saída 3

14