github.com/captn3m0/codechef.git

---
category_name: hard
problem_code: KOL1511
problem_name: 'Wait for it'
languages_supported:
    - C
    - CPP14
    - JAVA
max_timelimit: '3'
source_sizelimit: '50000'
problem_author: piyushkumar
problem_tester: null
date_added: 14-12-2015
tags:
    - acm15kol
    - euclidean
    - eulerian
    - gcd
    - piyushkumar
    - totient
editorial_url: 'http://discuss.codechef.com/problems/KOL1511'
time:
    view_start_date: 1420050600
    submit_start_date: 1420050600
    visible_start_date: 1420050600
    end_date: 1735669800
    current: 1493556745
layout: problem
---
All submissions for this problem are available.Given **N**, **A** and **B**, find the value of the following expression:

![](http://www.codechef.com/download/ACM15KOL/eqn.png)

Since the value can be large, find it **modulo (109+7).**

### Input

- The first line of the input contains an integer **T** denoting the number of test cases. The description of **T** test cases follows.
- Each test case consists of a single line containing three space-separated integers — **A**, **B**, and **N**.

### Output

- For each test case, output a single line containing the value of the expression **modulo 109+7**.

### Constraints

- **1** ≤ **T** ≤ **20**
- **1** ≤ **N** ≤ **109**
- **1** ≤ **B** < **A** ≤ **109**
- **GCD(A,B) = 1, i.e., A and B are coprime.**

### Example

<pre><b>Input:</b>
2
3 2 2
2 1 2

<b>Output:</b>
8
6
</pre>### Explanation

**Example case 1.**The summation expands to gcd(1,1) + gcd(5,1) + gcd(1,5) + gcd(5,5) = 8.

**Example case 2.**The summation expands to gcd(1,1) + gcd(3,1) + gcd(1,3) + gcd(3,3) = 6.