Thành phố Anpha có \(n\) địa danh đánh số từ 1 tới \(n\). Tại mỗi địa danh \(i\ (1 \leq i \leq 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 \leq n\) và tồn tại số nguyên dương \(j\) không quá \(x_{i}\) sao cho \(t = i + j.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 \ldots \rightarrow p_{k}\) và \(q_{1} \rightarrow q_{2} \rightarrow \ldots \rightarrow q_{h}\) gọi là khác nhau nếu \(k
eq h\) hoặc tồn tại \(i\ (2 \leq i \leq k)\) sao cho \(p_{i}
eq 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\ \left( 1 \leq n \leq 10^{5} \right)\);

• Dòng thứ \(i\ (1 \leq i \leq n)\) trong \(n\) dòng tiếp theo chứa 2 số nguyên \(d_{i},\ x_{i}\ \left( 0 \leq d_{i},x_{i} \leq 10^{9} \right)\).

Kết quả: ghi một số nguyên là số dư khi \(T\) chia cho \(10^{9} + 7\).

Ví dụ:

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

• \(1\)

• \(1 \rightarrow 2\)

• \(1 \rightarrow 2 \rightarrow 4\)

• \(1 \rightarrow 2 \rightarrow 4 \rightarrow 5\)

• \(1 \rightarrow 3\)

Ràng buộc:

• Subtask 1: 10% số test và số điểm có: \(n \leq 1000\);

• Subtask 2: 30% số test và số điểm có: \(d_{i} = 1\) với \(i = 1,2,\ldots,n\);

• Subtask 3: 30% số test và số điểm có: \(x_{i} = n\) với \(i = 1,2,\ldots,n\);

• Subtask 4: 30% số test và số điểm: không có giới hạn gì thêm.