GuGuFishtion

Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1008 Accepted Submission(s): 175

Problem Description

Today XianYu is too busy with his homework, but the boring GuGu is still disturbing him!!!!!!
At the break time, an evil idea arises in XianYu's mind.
‘Come on, you xxxxxxx little guy.’
‘I will give you a function

G u (a, b) = ϕ ( a b ) ϕ ( a ) ϕ ( b )

(\sum a = 1 m \sum b = 1 n G u (a, b))

Input

Input contains an integer

Output

Please output exactly

Sample Input

1
5 7 23

Sample Output

2

SequenceTime Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1782    Accepted Submission(s): 377


Problem Description
Let us define a sequence as below

⎧⎩⎨⎪⎪⎪⎪⎪⎪F1F2Fn===ABC⋅Fn−2+D⋅Fn−1+⌊Pn⌋


  Your job is simple, for each task, you should output Fn module 109+7.
 

Input
The first line has only one integer T, indicates the number of tasks.

Then, for the next T lines, each line consists of 6 integers, A , B, C, D, P, n.

1≤T≤200≤A,B,C,D≤1091≤P,n≤109
 

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

Sample Output
36
24
 
v judge 练习题
A - Round HouseVasya lives in a round building, whose entrances are numbered sequentially by integers from 1 to n. Entrance n and entrance 1 are adjacent.
Today Vasya got bored and decided to take a walk in the yard. Vasya lives in entrance a and he decided that during his walk he will move around the house b entrances in the direction of increasing numbers (in this order entrance n should be followed by entrance 1). The negative value of b corresponds to moving |b| entrances in the order of decreasing numbers (in this order entrance 1 is followed by entrance n). If b = 0, then Vasya prefers to walk beside his entrance.
 Illustration for n = 6, a = 2, b =  - 5. Help Vasya to determine the number of the entrance, near which he will be at the end of his walk.

Input
The single line of the input contains three space-separated integers n, a and b (1 ≤ n ≤ 100, 1 ≤ a ≤ n,  - 100 ≤ b ≤ 100) — the number of entrances at Vasya's place, the number of his entrance and the length of his walk, respectively.


Output
Print a single integer k (1 ≤ k ≤ n) — the number of the entrance where Vasya will be at the end of his walk.


Examples

   Input
  
6 2 -5
Output
3
Input
5 1 3
Output
4
Input
3 2 7
Output
3

Note
The first example is illustrated by the picture in the statements.

 1 #include<stdio.h>
 2 
 3 int main()
 4 {
 5     int n;
 6     int a,b;
 7     int ans;
 8     scanf("%d%d %d",&n,&a,&b);
 9     if(b<0)
10     {
11         int s=b%n;
12         if(s==0) ans=a;
13         else{
14         ans=a+(n+(b%n));
15         if(ans>n)
16         ans=ans%n;}
17     }
18     else if(b==0)  ans=a;
19     else
20     {
21 
22         ans=a+(b%n);
23         if(ans>n)  ans=ans%n;
24     }
25     printf("%d
",ans);
26     return 0;
27 }