该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

北武当山主峰四周几乎都是陡壁悬崖，只有一条人造“天梯”可攀，天梯由 n 级就山凿筑的石阶组成，欢欢打算通过天梯攀上北武当山主峰。攀天梯时，他有时一步一级石阶，有时一步两级，那么，他攀上这 n 级的天梯有多少种不同的方法？

Format

Input

一个整数 n（1 ≤ n ≤ 80）。

Output

一个整数，表示欢欢攀上这 n 级天梯的方法数。

Samples

5

8