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
(Tjandra Satria Gunawan)(曾毅昆): 2012-04-10 04:41:14

@Zhiang: for n=10000 ans is 2090 digits long :P

Sharavana guru: 2012-04-03 09:18:31

Yup :) i got the logic, Analyze your solution...

Zhiang: 2012-03-30 22:25:27

for n=10000 ans is 998 digits long !!!

B.R.ARVIND: 2012-03-29 15:40:17

move to tutorial or atleast dont accept submissions in java

BOND: 2012-03-05 04:07:42

analyze your solution.. there is something special :)

MR. BEAN : 2012-03-02 19:31:58

ans for n=1000 is 210 digit long :)

Jared Deckard: 2012-02-23 01:33:02

got AC, tried to bisect the solution set and my time increased... must not be very many large cases.

Rachmawan Atmaji Perdana: 2012-02-22 03:36:36

The answer is too long...

RAJDEEP GUPTA: 2012-02-21 17:39:02

I assumed that the answer is at most 2100 digits long.

krabathor: 2012-02-20 21:55:56

should be moved to tutorial


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