피보나치수는 첫째 항 및 둘째 항이 1이며, 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.
처음 여섯 항은 각각 1, 1, 2, 3, 5, 8 이다.
숫자 K를 입력 받아 K번째에 해당하는 피보나치 수를 출력하는 알고리즘을 작성 하시오.

첫 번째 줄에 정수 K가 입력된다.
(1 <= K <= 30)

첫 번째 줄에 K번째 피보나치 숫자를 출력한다.