Два нуля в двоичном числе

В двоичной системе счисления дано число с n цифрами. Первая и последняя цифры этого числа — единицы. Между любыми двумя единицами может быть не более двух нулей. Необходимо определить, сколько существует таких чисел.

Входные данные

Считать со стандартного ввода значение n, где 1 ≤ n ≤ 50.

Выходные данные

Вывести на стандартное устройство вывода количество чисел, удовлетворяющих указанным условиям.

Примеры