Counting Consecutive Sums

Time limit

Memory limit

32 MB

Problem

You are given a natural number N. Count how many ways N can be written as the sum of one or more consecutive natural numbers.

Every number used in the sum must be a natural number between 1 and N, inclusive. For example, 15 can be written in four ways: 15, 7+8, 4+5+6, and 1+2+3+4+5. The number 10 can be written in two ways: 10 and 1+2+3+4.

Input

The first line contains an integer N.

1 ≤ N ≤ 10,000,000

Output

Print the number of ways to write N as the sum of one or more consecutive natural numbers.