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
ameyanator: 2018-03-24 20:48:46

easy dp problem but my mind whirled around when i saw the answer for n=10000 :P

dunjen_master: 2018-01-04 19:07:19

python rocks!!

Rakend Chauhan: 2017-07-08 13:50:31

big integer really not likes me :(

cms118: 2017-06-13 15:19:25

BigInteger Rocks!!

kshubham02: 2017-03-28 08:16:23

5 lines in Python.
YES.
F-I-V-E LINES!

mukul arora: 2017-02-25 20:45:54

Python would be good.

prasoonbatham: 2017-01-16 18:19:02

Iterative dp + BigInteger in Java :)

vengatesh15: 2016-12-31 10:45:06

Thanks for the problem learnt how to use BIGINT

ndv17: 2016-08-22 10:42:11

:D

mkfeuhrer: 2016-07-11 21:06:47

easy in python if u get the dp relation!


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