#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Recursion (Fibonacci) - Classic Problems | Repovive

CLS2. Recursion (Fibonacci)

1s256 MB

The Fibonacci sequence is defined as:

$F_0 = 0$
$F_1 = 1$
$F_n = F_{n-1} + F_{n-2}$ for $n \ge 2$

Given $n$ , compute $F_n$ .

Constraints

$0 \le n \le 30$

Input

$n$

Output

$F_n$

Samples

Input

Explanation

For this input, the required output is 0.

Output

Input

Explanation

For this input, the required output is 1.

Output

Input

Explanation

For this input, the required output is 2.

Output

Input

Explanation

For this input, the required output is 5.

Output

The Fibonacci sequence is defined as:

$F_0 = 0$
$F_1 = 1$
$F_n = F_{n-1} + F_{n-2}$ for $n \ge 2$

Given $n$ , compute $F_n$ .

$0 \le n \le 30$

$F_n$