Nghỉ trưa sau ca trực trên thiên đình, Quan Văn và Quan Vũ cùng nhau chơi cờ. Đang trong thế bí, bất chợt Văn đánh đố Vũ: "Tại hạ có một câu đố cổ như sau. Trên một bàn cờ khổng lồ chia thành lưới ô vuông gồm \(n\) hàng và \(m\) cột. Nếu ta đặt 1 hạt thóc vào ô đầu tiên của hàng thứ nhất, 2 hạt vào ô thứ hai, 4 hạt vào ô thứ ba. Tiếp tục điền hết hàng 1 thì sang hàng 2, hết hàng 2 sang hàng 3... và tới cuối cùng là hàng thứ \(n\); sao cho ô tiếp theo luôn có số hạt thóc gấp đôi số lượng đặt vào ô trước đó. Dưới hạ giới nghiên cứu bài toán này 200 năm qua nên đã tính được tổng số hạt thóc trên bàn cờ này rồi, khà khà! Nhưng, Quan Vũ ngươi có tính được tổng số hạt thóc nằm trên cột thứ \(c\) là bao nhiêu không?". Vũ rơi vào trầm tư, trong thoáng chốc đã hết buổi chiều. Hắn buồn bực, hất đổ bàn cờ. "Cho ta 3 ngày, ta sẽ quay lại với đáp án chính xác". Thế là hắn đạp mây xé gió, bay xuống hạ giới, tới kỳ thi chọn HSG 9 của thành phố Đà Nẵng, nơi có rất nhiều tài năng toán học và lập trình để cầu cứu.

Yêu cầu: Cho \(n, m\) và \(c\). Hãy tính tổng số hạt thóc nằm trên toàn bộ cột thứ \(c\) của bàn cờ. Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho \(10^9+7\).

Input

Đọc từ tệp văn bản CHESS.INP:

• Một dòng duy nhất chứa ba số nguyên dương \(n, m\) và \(c\) (\(1 \le c \le m\)).

Output

Đọc ra tệp văn bản CHESS.OUT:

• Một số nguyên duy nhất là kết quả của bài toán chia lấy dư cho \(10^9+7\).

Example

3 3 2

146

Scoring

• Subtask 1 (\(30\%\) số điểm): \(n, m \le 1000\).
• Subtask 2 (\(30\%\) số điểm): \(n \le 10^5, m \le 10^{18}\).
• Subtask 3 (\(40\%\) số điểm): \(n \le 10^{18}, m \le 10^{18}\).