Với các tham số nguyên \(A\), \(B\), \(k\) cho trước, ta định nghĩa một dãy số nguyên dương là dãy đẹp nếu nó thỏa mãn các điều kiện sau:

• Có đúng \(2k\) phần tử (đánh chỉ số từ \(1\) đến \(2k\)).
• Tích của \(k\) phần tử đầu (có chỉ số từ \(1\) đến \(k\)) không vượt quá \(A\).
• Tích của tất cả \(2k\) phần tử đúng bằng \(B\).

Ví dụ: với \(A=4\), \(B=8\), \(k=2\) thì \([2, 2, 1, 2]\) là một dãy đẹp vì \(2\cdot 2=4\leq A\) và \(2\cdot 2\cdot 1\cdot 2=B\). Tương tự, \([1, 1, 1, 8]\) và \([1, 2, 1, 4]\) cũng là hai dãy đẹp. Ngược lại, \([4, 2, 1, 1]\) không phải là dãy đẹp vì \(4\cdot 2=8>A\).

Nhiệm vụ của bạn là lập trình tính số lượng dãy đẹp khác nhau ứng với từng input \(A\), \(B\), \(k\) được nhập vào. Hai dãy \(X\) và \(Y\) được coi là khác nhau nếu độ dài của chúng khác nhau, hoặc tồn tại một chỉ số \(i\) sao cho \(X_i\ne Y_i\). Vì kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư của nó khi chia cho \(1000000007\) (\(10^9+7\)).

Input

• Một dòng duy nhất chứa ba số nguyên dương \(A\), \(B\) và \(k\). (\(1\leq A\leq B\leq 10^9\), \(1\leq k\leq 10^5\))

Output

• Một số nguyên duy nhất là kết quả tìm được.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(A \leq B\leq 10\), \(k\leq 10\).
• Subtask \(2\) (\(25\%\) số điểm): \(B\) là một lũy thừa của \(2\) và \(k\leq 10\).
• Subtask \(3\) (\(25\%\) số điểm): \(B\) là một lũy thừa của \(2\) và \(k\leq 1000\).
• Subtask \(4\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Example

4 8 2

16

4 8 4

100