Quân là một coder Tài năng, anh là một trong những Tester cho chiếc máy tính lượng tử của Google. Thuật toán tính bằng qBit của máy tính lượng tử rất phức tạp và có tính xác suất (Có thể sai), vì vậy anh sẽ kiểm tra tính đúng trong phép tính của hệ thống cơ số lớn qBit của máy bằng bài toán sau:

"Cho ba số nguyên ~a,b,c~. Hãy tính:

Bài toán trên hoàn toàn có thể giải bằng một máy tính thường, song Quân là nhân viên của một công ti máy tính lớn hàng đầu thế giới nên anh không mang theo máy tính cá nhân ¯_(ツ)_/¯

Yêu cầu: Bạn hãy giúp Quân tính đáp án của bài toán trên để anh có thể test máy tính lượng tử nhé (Bạn có máy tính mà đúng khum ?). Vì đáp án của bài toán có thể rất lớn nên hãy in ra số dư khi chia cho ~10^9+7~

Input Format

Một dòng duy nhất chứa ba số nguyên ~a,b,c~ (~1 \le a,b,c \le 10^{12}~)

Output Format

Một số nguyên duy nhất là đáp án của bài toán

Sample Input 1

1 2 3

Sample Output 1

1

Sample Input 2

4 5 6

Sample Output 2

3

Sample Input 3

1 100000000 100000000

Sample Output 3

565378460