F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist

C/C++/Java Exams
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
DIY | Web-DIY beta
Register new ID

# Unknown Treasure

Time Limit: 1500/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 5082    Accepted Submission(s): 1794

Problem Description
On the way to the next secret treasure hiding place, the mathematician discovered a cave unknown to the map. The mathematician entered the cave because it is there. Somewhere deep in the cave, she found a treasure chest with a combination lock and some numbers on it. After quite a research, the mathematician found out that the correct combination to the lock would be obtained by calculating how many ways are there to pick $m$ different apples among $n$ of them and modulo it with $M$. $M$ is the product of several different primes.

Input
On the first line there is an integer $T (T \leq 20)$ representing the number of test cases.

Each test case starts with three integers $n, m, k (1 \leq m \leq n \leq 10^{18}, 1 \leq k \leq 10)$ on a line where $k$ is the number of primes. Following on the next line are $k$ different primes $p_1, . . . , p_k$. It is guaranteed that $M = p_1 ， p_2 ， ， ， p_k ＋ 10^{18}$ and $p_i \leq 10^5$ for every $i （ \{1, . . . , k\}$.

Output
For each test case output the correct combination on a line.

Sample Input
1
9 5 2
3 5


Sample Output
6

Source

Statistic | Submit | Discuss | Note
 Home | Top Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2024 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.000000(s) query 1, Server time : 2024-04-15 23:17:51, Gzip enabled Administration