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
Author ID 
Password 
 Register new ID

Simple Matrix

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 669    Accepted Submission(s): 222


Problem Description
As we know, sequence in the form of $a_n=a_1+(n-1)d$ is called arithmetic progression and sequence in the form of $b_n=b_1 q^{n-1}(q>1, b_1¡Ù0)$ is called geometric progression. Huazheng wants to use these two simple sequences to generate a simple matrix. Here is what he decides to do:
Use the geometric progression as the first row of the simple matrix: $c_{0,n}=b_n$
Use the arithmetic progression as the first column of the simple matrix: $c_{n,0}=a_n$
Calculate the item at $n$-th row, $m$-th column of the simple matrix as $c_{n,m}=c_{n-1,m}+c_{n,m-1}$, where $n¡Ý1$ and $m¡Ý1$.
Given the two sequences, Huazheng wants to know the value of $c_{n,m}$, but he is too busy with his research to figure it out. Please help him to work it out. By the way, you can assume that $c_{0,0}=0$.
 

Input
The first line of input contains a number $T$ indicating the number of test cases ($T¡Ü200$).
For each test case, there is only one line containing six non-negative integers $b_1,q,a_1,d,n,m$. ($0¡Ün¡Ü10000$). All integers are less than $2^{31}$.
 

Output
For each test case, output a single line consisting of ¡°Case #X: Y¡±. $X$ is the test case number starting from 1. $Y$ is $c_{n,m}$ module 1000000007.
 

Sample Input
2 3 10 1 1 3 3 5 2 1 10 4 2
 

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

Source
 

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-10-31 09:11:35, Gzip enabled