依古比古是OP

题号：NC232182
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

依古比古喜欢原神。

为了更好的管理角色，依古比古给每个角色赋了一个权值，构成一个权值序列 $a_i$ 。

不幸的是，依古比古的记性并不好，他甚至忘记了序列 $a_i$ 具体长啥样，只记得序列 $a_i$ 是一个长度为 $n$ 的严格单调递增的正整数序列，且满足 $1\leq a_i\leq m$ 。

同时，为了方便管理，依古比古实现了一个奇怪的算法：

容易看出，这个算法的作用是找到序列 $a_i$ 中第一个大于 $x$ 的位置。

现在，依古比古给出了 $q$ 次询问 $x_i$ ，他想要知道在所有可能的序列 $a_i$ 上运行 Search(x[i]) 调用 Check 函数的次数的和。

由于答案和输出量很大，令第 $i$ 次询问的答案为 $w_i$ ，你只需要输出（ $\oplus$ 表示异或）： $\bigoplus_{i=1}^{q}i(w_i\bmod 1000000007)$ ，即 $i\times (w_i\bmod 1000000007)$ 的异或和。

输入第一行三个整数 $n,m,q$ ( $1\leq n,m,q\leq 10^6$ ) ，分别表示序列长度、序列中元素的范围和询问次数。

第二行 $q$ 个整数 $x_i$ ( $0\leq x_i\leq m$ )，表示询问。

  输出一行一个整数表示压缩后的答案。

示例1

复制

3 4 5
0 1 2 3 4

复制

。