补幺梨
题号：NC229192
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

传说中，早在公元前 年，有个神秘的国家，叫做补幺国。他们当时就已在用一种叫做“补幺梨”的货币，其因形状长得像梨子而得名。
补幺人通过“补幺梨”货币来进行交易。具体地，“补幺梨”有 n 种面值，分别为 。
补幺人认为，在他们的视野里，m 是“补幺梨”基本面值的上限。因此，他们为了尽可能让这些基本的面值能覆盖所有面额，这 种面值是在 内等概率随机的。
补幺国王掌管大权，每种”补幺梨“他都有 枚。但是，即便他拥有再多的硬币，他还是很惊叹竟然有这些”补幺梨“凑不出的面额！
古人的智商自然是有限的，因此他们只能意识到问题，但不能解决问题。
作为十万年后的我们，古人借助时光机向我们发出求助。你需要帮他们计算出最大的不能被表示的面额。

输入描述:

 第一行，输入三个数  ，表示“补幺梨”的面值种数，基本货币的金额上限，以及随机种子。 
 
 对于 ，“补幺人”通过下述 c++ 程序的 mt19937 随机数得到（需 c++11）： 
 
 
int main() {
  scanf("%d%d%d", &n, &m, &seed);
  mt19937 rng(seed);
  auto get = [&]() {
    uniform_int_distribution<int> qwq(2, m);
    return qwq(rng);
  };
  for (int i = 1; i <= n; i++) {
    a[i] = get();
  }
}

输出描述:

你需要帮补幺人计算出最大不能被表示的面额。
不难发现，在给定的数据范围下，必定存在不能被表示的面额。
示例1

输入

复制 
5 5 3

输出

复制 
1

说明

注意，样例仅作为参考。该数据范围不会出现在最终测试数据中。
生成的序列为4 2 4 5 3。最大不能被表示的金额显然是1。
示例2

输入

复制 
2 100 10

输出

复制 
2309

说明

生成的序列为78 31。最大不能被表示的金额是2309。
示例3

输入

复制 
3 100 10

输出

复制 
89

说明

生成的序列为78 31 4。最大不能被表示的金额是89。
示例4

输入

复制 
50 50000000 97

输出

复制 
50215765

备注:

对于  的数据，；
对于  的数据，；
对于  的数据，；
对于  的数据，；
对于  的数据，；
对于所有数据，均满足  且 。