该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

有一个数组满足： $a_i = i ^ k$ mod $p$ 。

求整个数组 ($a_1$ 到 $a_n$) 的异或和。

Format

Input

一行三个正整数， $n(\le10^7)$ 、 $k(\le10^9)$ 和 $p(\le1.1\times10^9)$ 。

Output

一个整数，所有 $a_i = i ^ k$ mod $p$ 的异或和。

Samples

114 514 1000000007

1047501695

Limitation

1s, 1024KiB for each test case.