You cannot submit for this problem because the homework's deadline is due.

Description

Find the exact number of
1. the nth Fibonacci Number
2. \(2^n\).

Format

Input

Two integers \(s\) and \(n\), satisfying \(1\le s\le 2,0 \le n \le 2000\).

Output

If \(s=1\), print the nth Fibonacci Number.
If \(s=2\), print \(2^n\).

Sample 1

Input

1 100

Output

354224848179261915075

Sample 1

Input

2 100

Output

1267650600228229401496703205376