#P18172. An Easy Counting Problem
An Easy Counting Problem
An Easy Counting Problem
给定整数 ,求满足以下条件的整数数对 的数量:
输出数量对 取模的结果。
输入格式
一行三个整数 。其中 以二进制表示给出,从最高位开始,第一位保证为 1; 以通常的十进制给出。
满足
$$1\le k\le2^{1000},\qquad2\le p\le5000,\qquad1\le x<p.$$保证 是素数。 时,其二进制表示为 1 后跟 1000 个 0,共 1001 位。
注意:条件中的 是 的 次方; 的输入形式是二进制,不是十进制字符串。模组合数时使用 ,最终计数使用另一个模数 。
输出格式
输出一个整数,表示满足条件的数对数量模 的结果。
样例 1
输入:
1 7 5
输出:
2
样例 2
输入:
1 43 17
输出:
17
样例 3
输入:
1111111111 4999 1954
输出:
195378837