Farmer John разводит коров. Современные технологии используют давно умерших призовых быков, поэтому быки не нужны. Количеством корма он управляет числом телят; всем даёт одинаково, значит телят одинаковое число. Начав с одной коровы, хочет через несколько поколений получить $N$.

Если $N = 12$, первой корове даёт корм для трёх телят. Когда следующее поколение созреет, каждой даёт корм для четырёх телят, получая двенадцать. Родившую корову продают, оставляют только последнее поколение.

В каждом поколении корова рождает не меньше двух телят без верхней границы: порода очень сильная.

Для целого $N$ ($1 \le N \le 2{,}000{,}000{,}000$) сколько разных способов из одной коровы получить $N$? Число способов получить $N$ не превышает $2{,}000{,}000{,}000$.

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

• Строка 1: целое $N$.

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

• Строка 1: число способов получить $N$ коров.

Примеры

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

12

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

8

Примечание

Пояснение выходных данных

Способ получить двенадцать — $(2,2,3)$: по два телёнка в первом поколении, два во втором, три в третьем, всего двенадцать молодых телят. Другие семь: $(2,3,2)$, $(3,2,2)$, $(3,4)$, $(4,3)$, $(12)$, $(2,6)$, $(6,2)$.

Автор: Mihai Stroe, 2002