Easy Equation

Time limit1sMemory limit64 MB

Summary

Count the number of positive integer 5-tuples (x,y,z,w,t) with x^5 + y^4 + z^3 + w^2 + t = n, for n up to 1e9.

Level: Medium6 of 10
Topics: Math, Brute force, Implementation, Hash map
Solved: No attempts yet

Problem

Find the number of solutions of the equation $x^5 + y^4 + z^3 + w^2 + t = n,$ where $x$ , $y$ , $z$ , $w$ , and $t$ are positive integer variables, and $n$ is a given positive integer.

Input

A single line contains the integer $n$ ( $1 \le n \le 10^9$ ).

Output

Print the number of solutions on a single line.

Examples3

Example 1
Input
```
12
```
Expected output
```
3
```
Example 2
Input
```
2019
```
Expected output
```
7386
```
Example 3
Input
```
1000000
```
Expected output
```
26734730
```