Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Kai’Sa học rất giỏi và được nhà trường cho đến tham dự hội trại sinh viên nằm trên bãi biển Sầm Sơn.

Thật không may, thời điểm diễn ra hội trại có gió mạnh và hội trại có nguy cơ bị phá hủy. Tòa nhà của hội trại có thể biểu diễn dưới dạng một hình chữ nhật với chiều cao gồm n + 2 khối bê tông và chiều rộng gồm m khối bê tông.

Vào mỗi ngày sẽ có một làn gió thổi từ biển vào. Mỗi khối, ngoại trừ các khối ở trên cùng và dưới cùng của tòa nhà, sao cho không có khối nào ở bên trái nó sẽ bị phá hủy với xác suất là p = a / b. Tương tự vào mỗi đêm sẽ có một làn gió thổi ra biển. Mỗi khối, ngoại trừ các khối ở trên cùng và dưới cùng của tòa nhà, sao cho không có khối nào ở bên phải nó sẽ bị phá hủy với xác suất là p. Lưu ý, các khối ở trên cùng và dưới cùng của tòa nhà không thể bị phá hủy nên có n * m khối có thể bị phá hủy.

Chu kì gió kéo dài trong k ngày và k đêm. Trong thời gian này, nếu tòa nhà bị chia thành ít nhất hai phần riêng biệt nó sẽ bị sụp đổ và hội trại sẽ kết thúc sớm.

Tìm xác suất mà hội trại sẽ không phải kết thúc sớm.

Input

Dòng đầu tiên gồm hai số nguyên n và m (1 <= n, m <= 1500) biểu diễn kích thước của tòa nhà.

Dòng thứ hai chứa hai số nguyên a và b nguyên tố cùng nhau (1 <= a <= b <= 10^9) biểu diễn xác suất p.

Dòng thứ ba chưa số nguyên k (0<= k <= 100000) biểu diễn số ngày đêm gió thổi mạnh.

Output

Xem xác suất cần tìm là một phân số tối giản c / d. In ra một số nguyên bằng c * d^(-1) mod 10^9 + 7.

Example

Test 1:
Input:
2 2
1 2
1
Output:
937500007

Test 2:
Input:
4 3
1 7
5
Output:
147531854

Giải thích test 1:
Có 7 trường hợp tòa nhà không bị sụp đổ. Xác suất tòa nhà bị sụp đổ sẽ là 7 / 16. Vì vậy đáp án của bài toán là 7 * 16 ^ (-1) = 937500007 (mod 10^9 + 7).