Tại xứ sở thần tiên Alpha có ~n~ chú thỏ đang thu hoạch cà rốt. Chú thỏ thứ ~i~ (~1 \le i \le n~) bắt đầu thu hoạch ở vị trí ~x_i~ và thực hiện ~m_i~ bước nhảy, mỗi bước nhảy được đúng ~k_i~ đơn vị độ dài; chú thỏ thứ ~i~ có cách thu hoạch cà rốt như sau:

• Ở vị trí bắt đầu ~x_i~, thỏ thu hoạch được ~x_i~ củ cà rốt;
• Ở lần nhảy thứ nhất, thu hoạch được ~x_i + k_i~ củ cà rốt;
• Ở lần nhảy thứ ~t~ (~2 \le t \le m_i~), số cà rốt thu hoạch được nhiều hơn ~k_i~ củ cà rốt so với lần nhảy thứ ~t - 1~.

Yêu cầu: Tính tổng số cà rốt thu hoạch xong. Số lượng cà rốt thu hoạch có thể rất lớn nên chỉ cần đưa ra kết quả sau khi đã lấy phần dư cho ~(10^9 + 7)~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 10^6~).
• Trong ~n~ dòng tiếp theo, dòng thứ ~i~ (~1 \le i \le n~) chứa 3 số nguyên dương ~x_i, m_i, k_i~ (~1 \le x_i, m_i, k_i \le 10^9~).

Output

• Ghi ra một số nguyên duy nhất là kết quả bài toán.