异或求和：n对1~n的模值异或和

题目描述

给定正整数 $n$（$1 \le n \le 10^{12}$），求表达式 $(n \bmod 1) \oplus (n \bmod 2) \oplus (n \bmod 3) \oplus \ldots \oplus (n \bmod n)$ 的值。其中 $\oplus$ 表示按位异或运算。

输入格式

一行一个正整数 $n$。

输出格式

一行一个正整数，表示上述表达式的结果。

样例输入

10

样例输出

7

数据范围与提示

• 对于 30% 的数据，$1 \le n \le 10^6$；
• 对于 100% 的数据，$1 \le n \le 10^{12}$。