Một chiếc máy bay đang ở độ cao ~h1~. Phi công cần điều khiển để máy bay đạt độ cao ~h2~ trong đúng ~n~ giây.

Tại mỗi giây, phi công có thể điều khiển bởi một trong ba lệnh: Tăng độ cao lên ~1~, giảm độ cao đi ~1~, giữ nguyên độ cao.

Hãy đếm số cách điều khiển khác nhau. Biết rằng máy bay có thể chạm vào mặt đất (độ cao ~0~) nhưng không thể đạt độ cao âm. Hai cách điều khiển được cho là khác nhau nếu tồn tại ~i~, ~1 ≤ i ≤ n~ sao cho lệnh điều khiển ở thời điểm thứ ~i~ trong hai cách trên là khác nhau.

Input

Dòng ~1~: Ghi ~3~ số nguyên dương ~h1, h2, n~ ~(h1, h2, n≤10^5)~.

Output

Dòng ~1~: Chứa kết quả của bài toán lấy dư cho ~10^9 + 7~.

Scoring

Sample Input 1

0 0 6

Sample Output 1

51