Коник-стрибунець стрибає по стовпчикам, розташованим на одній лінії на рівних відстанях один від одного. Стовпчики мають порядкові номери від 1 до \(N\). На початку Коник сидить на стовпчику з номером 1. Він може стрибнути на наступний стовпчик або відразу на другий стовпчик, рахуючи від поточного. Потрібно знайти кількість способів, якими Коник може дістатися стовпчика з номером \(N\) . Враховуйте, що Коник не може стрибати назад.

Формат вхідних даних

Вхідний рядок містить натуральне число \(N\) ( \(1 \le N \le 45\) ).

Формат вихідних даних

Програма повинна вивести одне число: кількість способів, якими Коник може дістатися стовпчика з номером \(N\) .

Приклад вхідних даних

3

Приклад вихідних даних

2

Приклад вхідних даних

10

Приклад вихідних даних

55