Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P185SUMD - ROUND 5D - Lát gạch

Thử thách ngày hôm nay đối với Lù nhà ta khá đơn giản như sau:

Có một khoảng sân hình chữ nhật có kích thước 2 x N ô vuông, gồm 2 hàng và N cột.  Đánh số hàng từ 1 đến 2 theo thứ tự từ trên xuống dưới, đánh số cột từ 1 đến n theo thứ tự từ trái qua phải. Lù phải lát sân bằng gạch màu trắng và điểm xuyết một số ô gạch màu đen, mỗi ô vuông được lát bởi một viên gạch, sao cho không có hai viên gạch màu đen nào chung cạnh với nhau. Hỏi có tất cả bao nhiêu cách khác nhau để lát khoảng sân trên (hai cách lát sân được gọi là khác nhau nếu tồn tại tối thiểu một ô ở dòng i cột j được lát gạch màu trắng ở cách này và lát gạch màu đen ở cách kia).

Ví dụ với n = 2, ta có 7 cách lát sân sau đây:

Input

Là một số nguyên n (1 ≤ n ≤ 5.103).

Output

Là số cách lát gạch theo yêu cầu. Số lượng cách có thể cách có thể rất lớn nên lấy dư cho 10+ 7.

Example

Input:
3

Output:
17

Được gửi lên bởi:Admin
Ngày:2018-08-03
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.