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

# Simple Matrix

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 662    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
 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-08-14 19:37:27, Gzip enabled Administration