The local police department has carefully selected you to help them with their new physical training program, specifically the tire run, an event where trainees are required to run through a straigt line of tires. The captain informs you that each trainee stands in front of the first tire and can either step in the next tire (directly in front of him/her) or the next-to-next tire (two in front of him/her). Unfortunately the police department doesn't know how many tires they expect to collect over the next month, but they have already collected around 20.
Given an integer n, find the number of possible ways a trainee can run across the line of n tires, keeping in mind they can only step in the next, or next-to-next, tire.
Given an integer n, find the number of possible ways a trainee can run across the line of n tires, keeping in mind they can only step in the next, or next-to-next, tire.
Input Format
One line containing an integer n, such that 20 < n < 100
Sample Input
75
Output Format One line containing a large integer representing the number of possible ways to run across the tire line
Sample Output
2111485077978050 You must be logged in to submit a solution.