Cho \(7\) số tự nhiên \(A, B, C, D, E, F, G\).

Hãy đếm số lượng bộ ba số nguyên \((x, y, z)\) thỏa mãn các điều kiện sau:

• \(A \le x \le B\)
• \(C \le y \le D\)
• \(E \le z \le F\)
• \((x + y + z)\) chia hết cho \(G\).

Do kết quả có thể rất lớn, hãy đưa ra kết quả sau khi chia lấy dư cho \(10^9 + 7\).

Input

• Một dòng duy nhất chứa \(7\) số tự nhiên \(A, B, C, D, E, F, G\) cách nhau bởi khoảng trắng \(0 \le A \le B \le 10^9, 0 \le C \le D \le 10^9, 0 \le E \le F \le 10^9, 1 \le G \le 3000)\).

Output

• Một số nguyên duy nhất là số lượng bộ ba thỏa mãn điều kiện sau khi chia lấy dư cho \(10^9 + 7\).

Example

1 3 2 4 5 5 3

3