Input

• Input is a sequence of lines, each line containing an integer number \(0 \le n \le 250\)

Output

• For each line of input, output one integer number in a separate line giving the number of possible tilings of a \(2 × n\) rectangle.

Example

Sample input

2
8
12
100
200

Sample output

3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251