Farmer John nhân giống bò. Kỹ thuật hiện đại dùng bò đực đoạt giải đã chết từ lâu nên không cần bò đực. Lượng thức ăn kiểm soát số bê; mọi con ăn bằng nhau nên sinh cùng số bê. Ông bắt đầu với một con và muốn $N$ con sau vài thế hệ.

Nếu $N = 12$, cho bò ban đầu ăn đủ để sinh ba bê. Khi thế hệ sau đủ tuổi sinh, mỗi con ăn đủ để sinh bốn, cuối cùng mười hai. Bò mẹ được bán sau khi sinh nên chỉ giữ thế hệ mới nhất.

Mỗi thế hệ mỗi bò sinh ít nhất hai bê, không có giới hạn trên, nhờ giống rất khỏe.

Cho số nguyên $N$ ($1 \le N \le 2{,}000{,}000{,}000$), có bao nhiêu cách khác nhau để từ một bò có $N$ bò? Số cách có $N$ bò không vượt $2{,}000{,}000{,}000$.

Dữ liệu vào

• Dòng 1: số nguyên $N$.

Dữ liệu ra

• Dòng 1: số cách có $N$ bò.

Ví dụ

Dữ liệu vào 1

12

Dữ liệu ra 1

8

Ghi chú

Giải thích dữ liệu ra

Một cách có mười hai là $(2,2,3)$: hai bê mỗi bò ở thế hệ đầu, hai ở thứ hai, ba ở thứ ba, tổng mười hai bê con. Bảy cách khác là $(2,3,2)$, $(3,2,2)$, $(3,4)$, $(4,3)$, $(12)$, $(2,6)$, $(6,2)$.

Tác giả: Mihai Stroe, 2002