题目描述

求 $1\%n+2\%n+3\%n+...+(10^9)\%n$ 的值。

输入格式

输入一个整数 $n$

输出格式

输出一个整数，表示答案

样例

2

500000000

1

0

4

1500000000

数据范围

对于 $30\%$ 的测试点，$1≤n≤3$。

对于所有测试点，$1≤n≤10^9$。