Problem description

Zbiór poprawnych nawiasowań można zdefiniować rekurencyjnie:

1. pusty napis jest poprawnym nawiasowaniem,
2. jeżeli X jest poprawnym nawiasowaniem to: (X) również jest poprawnym nawiasowaniem,
3. jeżeli P oraz Q są poprawnymi nawiasowaniami to PQ (sklejenie P i Q ze sobą) też jest poprawnym nawiasowaniem,
4. wszystkie poprawne nawiasowania można wyprowadzić za pomocą powyższych reguł.

Łatwo zauważyć, że każde poprawne nawiasowanie musi mieć parzystą długość. Dla ustalonego N, w miarę nietrudno też policzyć ile jest poprawnych nawiasowań długości 2N:

• dla N = 1 (nawiasowania długości 2) jest tylko jedno takie nawiasowanie: (),
• dla N = 2 (nawiasowania długości 4) są dwa takie nawiasowania: (()) oraz ()(),
• dla N = 3 (nawiasowania długości 6) jest pięć poprawnych nawiasowań: ((())), ()(()), (())(), (()()) oraz ()()().

W ogólności: liczba poprawnych nawiasowań o określonej długości jest ściśle związana z ciągiem liczb Catalana C_n. Jest dokładnie C_n poprawnych nawiasowań długości 2n.

Wzorów na obliczenie n-tej liczby Catalana jest wiele. Przykładowo takie:

• $C_n = \frac{1}{n+1} {2n \choose n}$,
• $C_n = \frac{1}{2n+1} {2n+1 \choose n}$,
• $C_n = {2n \choose n} - {2n \choose n+1}$,
• C₀ = 1, $C_n = \sum_{i=1}^n C_{i-1} C_{n-i}$ (dla n > 0),
• C₀ = 1, $C_n = \frac{4n-2}{n+1} C_{n-1}$ (dla n > 0).

W tym zadaniu rozszerzamy definicję poprawnych nawiasowań na większą liczbę typów nawiasów: w punkcie drugim definicji mówimy, że poprawne są również nawiasowania [X] oraz {X}. Rozważamy więc poprawne (uogólnione) nawiasowania złożone z nawiasów (, ), {, }, [, ]. Czy potrafisz powiedzieć ile jest uogólnionych poprawnych nawiasowań o długości 2N? Sprawdźmy to! Ponieważ wynik może być duży, wystarczy nam poznać jego resztę z dzielenia przez 10⁹ + 7.

Napisz program, który: wczyta liczbę N, wyznaczy resztę z dzielenia przez 10⁹ + 7 liczby uogólnionych poprawnych nawiasowań długości 2N, i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się jedna liczba naturalna N.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć reszta z dzielenia przez 10⁹ + 7.

Ograniczenia

1 ≤ N ≤ 2 000.

Ciekawostka: Możliwe jest rozwiązanie tego zadania dla znacznie większych limitów (np. organizatorzy turnieju potrafią napisać program, który mieści się w limitach czasu nawet przy ograniczeniu N ≤ 10¹¹). Ale to jest turniej dla początkujących. Zachęcamy do przemyślenia szczegółów po turnieju.

Przykład

2

18