Quang có \(n\) khối gỗ màu đỏ, mỗi khối có kích thước \(1 \times 1 \times a\) (cm) và \(m\) khối gỗ màu xanh, mỗi khối có kích thước \(1 \times 1 \times b\) (cm). Quang xếp các khối gỗ thành một cột thẳng đứng có đáy là một hình vuông kích thước \(1 \times 1\) (cm) và tiến hành đo chiều cao của cột gỗ, ký hiệu là \(h\). Quang thử tất cả các cách xếp khác nhau và ghi lại các giá trị \(h\) thu được.

Yêu cầu: Vì số lượng giá trị \(h\) mà Quang ghi lại được là quá lớn, bạn hãy giúp Quang đếm xem có bao nhiêu giá trị \(h\) khác nhau mà Quang đã tạo ra.

Input

• Nhập từ file WOOD.inp:
  • Một dòng duy nhất gồm bốn số nguyên dương \(a, b, n, m\) (\(1 \le a, b, n, m \le 10^9\)).

Output

• Ghi ra file WOOD.out:
  • Một dòng duy nhất là số giá trị \(h\) khác nhau mà Quang tạo được. Vì số giá trị có thể rất lớn nên chỉ cần in ra phần dư của nó khi chia cho \(10^9 + 7\).

Example

2 3 1 2

5

3 3 1 1

2

Ràng buộc bổ sung

• 20% số điểm có \(n = m = 1\).
• 20% số điểm khác có \(a = b\).
• 10% số điểm khác có \(m = 1\).
• 10% số điểm khác có \(n, m \le 10\).
• 10% số điểm khác có \(n, m \le 1000\).
• 10% số điểm khác có \(b = 1\).
• 10% số điểm khác có \(m \le 10^5\).
• 10% số điểm còn lại không có giới hạn gì thêm.