Thành phố Anpha có \(n\) địa danh đánh số từ \(1\) tới \(n\). Tại mỗi địa danh \(i\) (\(1 \le i \le n\)) có một tấm bảng hướng dẫn di chuyển ghi \(2\) số nguyên không âm \(d_i\) và \(x_i\): từ địa danh thứ \(i\) có thể đi tới địa danh \(t\) nếu \(i < t \le n\) và tồn tại số nguyên dương \(j\) không quá \(x_i\) sao cho \(t = i + j \cdot d_i\).

Một hành trình du lịch xuất phát từ địa danh \(1\), kết thúc tại một địa danh nào đó trong \(n\) địa danh.

Hai hành trình du lịch \(p_1 \rightarrow p_2 \rightarrow \cdots \rightarrow p_k\) và \(q_1 \rightarrow q_2 \rightarrow \cdots \rightarrow q_h\) gọi là khác nhau nếu \(k \ne h\) hoặc tồn tại \(i\) (\(2 \le i \le k\)) sao cho \(p_i \ne q_i\).

Gọi \(T\) là số lượng hành trình du lịch, tính số dư khi \(T\) chia cho \(10^9 + 7\).

Dữ liệu vào

• Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 10^5\));
• Dòng thứ \(i\) (\(1 \le i \le n\)) trong \(n\) dòng tiếp theo chứa 2 số nguyên \(d_i, x_i\) (\(0 \le d_i, x_i \le 10^9\)).

Dữ liệu ra

• Một số nguyên là số dư khi \(T\) chia cho \(10^9 + 7\).

Input 1

5
1 2
2 3
0 4
1 1
2 0

Output 1

5

Giải thích: Có 5 hành trình:

• 1
• 1 → 2
• 1 → 2 → 4
• 1 → 2 → 4 → 5
• 1 → 3

Ràng buộc:

• Subtask 1: 10% số test và số điểm có: \(n \le 1000\);
• Subtask 2: 30% số test và số điểm có: \(d_i = 1\) với \(i= 1,2, … , n\);
• Subtask 3: 30% số test và số điểm có: \(x_i = 1\) với \(i= 1,2, … , n\);
• Subtask 4: 30% số test và số điểm: không có giới hạn gì