Cho số nguyên dương \(n\), hãy tìm số fibonaci \(f(k(n))\) với \(k(n)\) là số nguyên tố thứ \(n\). Cho trước dãy fibonaci khởi đầu:

• \(f(0) = 1\).
• \(f(1) = 1\).
• \(f(2) = 2\). ...
• \(f(x) = f(x - 1) + f(x - 2)\).

Vì dữ liệu có thể quá lớn, in ra kết quả của số fibonaci khi chia dư cho \(10^9 + 7\).

INPUT FORMAT

1 dòng gồm số nguyên dương \(n(1 \leq n \leq 50)\).

OUTPUT FORMAT

In ra 1 số nguyên dương là số fibonaci thứ \(k(n)\).

Ví dụ:

Input

4

Output

21

Giải thích ví dụ mẫu:

Ví dụ:

Input:

4

Output:

21

Giải thích: Số nguyên tố thứ 4 là 7, và số Fibonacci thứ 7 là 21.

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House