提示: 欢迎访问OurACM平台。
Problem 2042 The Mad Mathematician

Accept: 97    Submit: 389
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

It was so easy to translate the pseudo code into some programming language. But soon, I found that for some inputs, which he gave me, it took huge time to get the result. In fact, it is easy to see that it may take years to get the output for some inputs when using the pseudo code above. "The sum may be huge, just give me the sum modulo 1,000,000,007. Enjoy the beauty of mathematics!” Bob said with a smile. And now, I’ll be graduating soon. I still can’t come up with any ideas with this problem. Will you help me to solve it?

Input

The first line of the input contains an integer T (T≤100), indicating the number of test cases. Each case begins with a line containing five integers A, B, C, D and E(0≤A, B, C, D, E≤2^63-1, A≤B, C≤D), the inputs of the pseudo code.

Output

For each test case, print a line containing the test case number (beginning with 1) and the result of the pseudo code modulo 1,000,000,007.

Sample Input

3 1 1 2 2 2 1 1 2 2 3 10 10 10 100 5

Sample Output

Case 1: 3 Case 2: 0 Case 3: 4985

Source

2011年全国大学生程序设计邀请赛(福州)

Submit  Back  Status  Discuss