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

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

Вхідні дані

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

Вихідні дані

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