Группа математиков проводит бои между натуральными числами. Результаты боя между двумя натуральными числами, вообще говоря, случайны, однако подчиняются следующему правилу: если одно из чисел не менее чем в два раза превосходит другое, то большее число всегда побеждает; в противном случае победить может как одно, так и другое число.

Бой называется неинтересным, если его результат предопределён. Множество натуральных чисел называется мирным, если бой любой пары различных чисел из этого множества неинтересен. Силой множества называется сумма чисел в нём. Сколько существует мирных множеств натуральных чисел силы n?

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

Одно число n (1 ≤ n ≤ 2000).

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

Выведите одно число - количество мирных множеств натуральных чисел силы n.