Shiba là anh chàng đam mê công nghệ. Trong một buổi tối, anh ta lướt qua một trang web về việc xây dựng các công trình dựa trên hình học và đọc về một khối hộp chữ nhật trong không gian ba chiều \(xyz\). Với kích thước \(A \times B \times C\), khối này được tạo thành bởi \(A \times B \times C\) khối lập phương có độ dài cạnh bằng \(1\).

Shiba cảm thấy thú vị và muốn thử xây dựng một mô hình của khối chữ nhật đó. Anh ta quyết định dùng các khối lập phương nhỏ để lắp ráp theo kích thước đã cho.

Nhưng Shiba cũng muốn kiểm tra xem liệu các khối lập phương đã được lắp ráp đúng cách hay không. Các khối lập phương đã được lắp ráp đúng cách khi với mỗi bộ tam số \(i, j, k\) \((0 \le i < A, 0 \le j < B, 0 \le k < C)\) luôn tồn tại một khối lập phương có đường chéo nối hai điểm \((i, j, k)\) và \((i+1, j+1, k+1)\) và chúng đều song song với các trục tọa độ.

Shiba bắt đầu suy nghĩ và tìm ra một cách để kiểm tra xem khối lập phương đã được lắp ráp đúng cách hay không. Anh ấy quyết định dùng một sợi dây để kéo dọc đường chéo của khối chữ nhật, từ điểm \((0, 0, 0)\) đến điểm \((A, B, C)\). Sau đó, Shiba muốn tìm số lượng các khối lập phương mà sợi dây đi qua bên trong chúng (lưu ý là không chỉ nằm trên bề mặt mà còn bên trong nó nữa) và khoảng cách giữa các khối đó và khối mà sợi dây đi qua không vượt quá \(S\).

Biết rằng khoảng cách giữa hai khối \((i_1,j_1,k_1)\) và \((i_2,j_2,k_2)\) được tính bằng \(max(|i_1-i_2|,|j_1-j_2|,|k_1-k_2|)\).

Yêu Cầu: Bạn hãy đếm và in ra số lượng các khối lập phương thỏa mãn yêu cầu đề bài.

Input

• Gồm các số nguyên lần lượt là \(A,B,C,S\) \((1 \le A < B < C \le 10^9, 0 \le S \le 5 \times 10^4)\).
• Dữ Liệu Vào luôn thỏa mãn có ít nhất hai số trong ba số \(A,B,C\) tạo thành số nguyên tố cùng nhau (số nguyên tố cùng nhau là hai số mà ước chung lớn nhất của chúng bằng \(1\)).

Output

• In ra đáp án bài toán sau khi chia lấy dư cho \(10^9+7\) \((1000000007)\).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): Có \(1\le A < B < C \le 100\) và \(S = 0\).
• Subtask \(2\) (\(50\%\) số điểm): Có \(100 < A < B < C \le 10^9\) và \(S = 0\).
• Subtask \(3\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 4 5 1

54