Fibonacci

  ลำดับฟีโบนักชี ( Fibonacci Sequence ) คือชุดของตัวเลขที่ตัวเลขถัดไปจะเป็นผลรวมของสองตัวก่อนหน้า โดยมีสองตัวแรกเป็น 0 และ 1 ตามลำดับ

ตัวอย่างลำดับฟีโบนักชี:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

ฟังก์ชันฟีโบนักชีสามารถกำหนดได้ดังนี้:

• F(0) = 0

• F(1) = 1

• F(n) = F(n - 1) + F(n - 2), $n>1$

งานของคุณ
  ให้จำนวนเต็มบวก $N$ จงหาจำนวนฟีโบนักชีลำดับที่ $N$

Input :

มี 1 บรรทัด : รับจำนวนเต็มบวก $N$

Output :

มี 1 บรรทัด : จำนวนฟีโบนักชีลำดับที่ $N$

Examples :

ตัวอย่างที่ 1

2 
            

1
            

ตัวอย่างที่ 2

5 
            

5
            

Constraints :

• $1 \leq N \leq 30$

Limits :

• Time limit : 1 second
• Memory limit : 256 MB