In a directed weighted graph, the vertices are numbered from 1 to n. If i<j, then there is an edge from vertex i to vertex j whose weight is determined by the formula \(wt(i,j)=(179i+719j)\ mod \ 1000 - 500 \). Determine the weight of the shortest path leading from vertex 1 to vertex n.
Input:
The program receives a single number n (2≤n≤13000) as input.
Output:
The program should output a single integer - the weight of the shortest path from vertex 1 to vertex n in the described column.
Examples
| # |
Input |
Output |
| 1 |
2 |
117 |
| 2 |
3 |
-164 |