华华给月月出题

题目描述

华华刚刚帮月月完成了作业。为了展示自己的学习水平之高超，华华还给月月出了一道类似的题： $Ans = \oplus_{i=1}^{N}(i^N mod (10^9 + 7))$ 符号表示异或和，详见样例解释。 虽然月月写了个程序暴力的算出了答案，但是为了确保自己的答案没有错，希望你写个程序帮她验证一下。

输入格式

输入一个正整数$N$

输出格式

输出答案$Ans$。

样例 #1

样例输入 #1

3

样例输出 #1

18

提示

样例一提示： $N=3$时，$1^3=1$，$2^3=8，3^3=27$，异或和为$18$。 备注 $1 \le N \le 1.3 × 10^7$