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

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

Вхідні дані

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

Вихідні дані

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

Вхідні дані #1

2

Відповідь #1

1

Вхідні дані #2

5

Відповідь #2

2