IWGBS - 0110SS


Dor is IWGolymp student so he has to count in how many ways he can make N digit numbers that is formed by ones and zeroes. But zeroes can not be next to each other. Help to him in how many different numbers can he make.

For example, N = 3: 101, 010, 111, 110, 011

Note: A leading zero is allowed.

Input

A positive integer N (1 <= N <= 10000).

Output

Answer for the problem.

Example

Input:
2

Output:
3

hide comments
Hasil Sharma: 2014-12-07 22:07:57

Phew !! Did it with C++ ... little hardwork but great confidence boost :)

pvkcse: 2014-08-30 13:44:28

Easy using Python...but still i can't get how to do this with c,cpp...

[Lakshman]: 2014-06-20 13:42:21

@shreya sahu your code is not giving correct output for sample input. For 10 answer is 144.

shreya sahu: 2014-06-20 13:08:14

failing at 6th judge. here is my code http://ideone.com/qS66Qt
please help

bahosain: 2014-05-02 00:54:37

@Crazzyy
The input has only one number

thangagiriarasan: 2013-11-01 07:45:48

easy to do in python than in c or c++

Ouditchya Sinha: 2013-05-26 12:59:11

Nice way of presenting the problem, for n = 10000, the answer is 2090 digits long. :)

Himanshu: 2013-05-24 11:22:53

why my code is giving wrong answer

Crazzyy: 2012-05-21 04:57:17

got AC....input has more than one number upto EOF

Last edit: 2012-05-21 05:02:17

Added by:Azat Taryhchiyev
Date:2012-02-16
Time limit:0.100s-3.085s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64