URI Online Judge | 2970

Keep Calm e Venda Balões

Por Maratona SBC de Programação BR Brazil

Timelimit: 1

Walter vende balões de porta em porta. Todo dia ele escolhe uma rua da sua cidade e visita todas as casas nela, oferecendo seus coloridos balões.

Cada rua da cidade de Walter tem a mesma quantidade de casas dos dois lados, e todas as casas da cidade são do mesmo tamanho. Dessa forma, cada rua pode ser vista como uma matriz 2 × N, onde cada célula é uma casa, e N é a quantidade de casas ao longo de cada lado da rua.

Depois de escolher a rua do dia, Walter visita cada casa dessa rua exatamente uma vez. Ele pode começar seu caminho em qualquer casa, mas só pode se mover entre casas adjacentes horizontalmente, verticalmente ou diagonalmente.

coffee

A tabela acima ilustra um exemplo para N = 6. Após visitar a casa de número 1, Walter só poderia seguir imediatamente para as casas de número 2, 7 e 8 (isto é, se ele já não tiver visitado elas antes). E após visitar a casa de número 11, a próxima casa do caminho só poderia ser uma das seguintes: 4, 5, 6, 10 ou 12.

Hoje, antes de sair de casa, Walter olhou o mapa da cidade para contar a quantidade N de casas de cada lado da rua escolhida. Agora ele quer saber de quantas maneiras distintas ele pode visitar todas as 2N casas da rua, seguindo as regras descritas. Duas maneiras de visitar as casas são diferentes se e somente se a ordem das casas varia: isto é, se existem duas casas A e B tais que A é visitada antes de B em uma ordem e B é visitada antes de A na outra.

Entrada

A entrada consiste de uma única linha que contém um inteiro N (1 ≤ N ≤ 109).

Saída

Seu programa deve produzir uma única linha com um inteiro representando o número de maneiras possíveis de visitar todas as casas da rua. Dado que este número pode ser muito grande, você deve fornecer o resto da divisão deste número por 109 + 7.

Exemplos de Entrada Exemplos de Saída

2

24

3

96

4

416

61728

654783381