Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
 Register new ID

Congruence equation

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 394    Accepted Submission(s): 111

Problem Description
There is a sequence $A$ which contains $k$ integers.
Now we define $f\left(m\right)$ is the number of different sequence $C$ that satisfies for $i$ from $1$ to $k$:
1. If $A_{i} = -1$, $C_{i}$ can be any integer in the range of $[0, m)$.Otherwise $C_{i} = A_{i} \pmod m$
2. $\sum\limits_{i = 1} ^{k} C_{i}x_{i} \equiv 1 \pmod m$($x_{i}$ are variables) have a solution in the range of integer.

Calculate the answer of $\sum\limits_{m = 1} ^{n} f(m) \pmod{10^9+7}$.

The first line contains only one integer $T ( T \leq 100)$, which indicates the number of test cases.
For each test case, the first line contains two integers $k$ and $n$.($1 \leq k \leq 50, 1 \leq n \leq 10^9$)
The second line contains $k$ integers: $A_{1}, A_{2} \dots A_{k}(-1 \leq A_{i} \leq 10^9)$
There are at most $10$ test cases which satisfies $n \geq 10^6$

For each test case, output one line "Case #x: y", where x is the case number (starting from 1) and y is the answer after mod 1000000007 ($10^9+7$).

Sample Input
2 5 10 -1 -1 8 -1 -1 3 20 -1 6 18

Sample Output
Case #1: 24354 Case #2: 140


Statistic | Submit | Discuss | Note
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-07-14 10:28:08, Gzip enabled