Sum of QQ

Time limit2sMemory limit512 MB

Summary

Count axis-parallel rectangles in the multiplication table whose entries sum to exactly S, with S up to 100000.

Level: Hard8 of 10
Topics: Math, Number theory, Brute force
Solved: No attempts yet

Problem

You received a card with an integer $S$ on it and a multiplication table of infinite size. Every element of the table is an integer, and the integer in the $i$ -th row from the top and the $j$ -th column from the left is $A_{i, j} = i \times j$ ( $i, j \ge 1$ ). The table is infinite: it has infinitely many rows and infinitely many columns.

You love rectangular regions of the table whose numbers sum to $S$ . Your task is to count the number of integer tuples $(a, b, c, d)$ such that $1 \leq a \leq b$ , $1 \leq c \leq d$ , and $\sum_{i=a}^{b} \sum_{j=c}^{d} A_{i,j} = S$ .

Input

The input consists of a single test case of the following form.

$S$

The first line contains one integer $S$ ( $1 \leq S \leq 10^5$ ), the sum of the rectangular regions you have to find.

Output

Print the number of rectangular regions whose sum is $S$ on one line.

Examples4

Example 1
Input
```
25
```
Expected output
```
10
```
Example 2
Input
```
1
```
Expected output
```
1
```
Example 3
Input
```
5
```
Expected output
```
4
```
Example 4
Input
```
83160
```
Expected output
```
5120
```