Vào ngày 28 tháng 3 năm 2025, một trận động đất kinh hoàng đã xảy ra tại Myanmar, gây ra thiệt hại nghiêm trọng về người và tài sản, đồng thời phá hủy phần lớn cơ sở hạ tầng, bao gồm cả hệ thống thông tin liên lạc. Đội cứu hộ Việt Nam, với tinh thần tương thân tương ái, đã nhanh chóng được cử đến hiện trường để hỗ trợ công tác tìm kiếm, cứu nạn và khắc phục hậu quả. Nhằm giúp Myanmar khắc phục hậu quả của trận động đất, đội cứu trợ Việt Nam đang tích cực phối hợp với chính quyền sở tại và người dân địa phương, khẩn trương triển khai các hoạt động cứu hộ, cứu trợ hiệu quả tại thành phố Mandalay.

Thành phố Mandalay được chia thành ~n~ khu vực cần hỗ trợ khẩn cấp, đánh số từ 1 tới ~n~. Tại khu vực ~i~ (~1 \le i \le n~) có đặt một bảng hướng dẫn cứu hộ ghi 2 số nguyên không âm ~d_i~ và ~x_i~, thể hiện cách thức di chuyển giữa các khu vực như sau: từ khu vực thứ ~i~ đội cứu hộ có thể di chuyển tới khu vực ~t~ nếu ~i < t \le n~ và tồn tại số nguyên dương ~j~ không vượt quá ~x_i~ sao cho ~t = i + j \times d_i~.

Một hành trình cứu hộ luôn xuất phát từ khu vực 1 và kết thúc tại một khu vực bất kỳ trong số ~n~ khu vực. Hai hành trình ~p_1 \to p_2 \to \dots \to p_k~ và ~q_1 \to q_2 \to \dots \to 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~.

Nhằm xây dựng kế hoạch cứu hộ tối ưu nhất, đội cứu hộ Việt Nam cần thống kê toàn bộ các hành trình có thể thực hiện. Gọi ~T~ là số lượng hành trình cứu hộ khả thi mà đội có thể triển khai.

Yêu cầu: Hãy tính số dư khi chia ~T~ cho ~10^9 + 7~.

Input

• 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~).

Output

• Kết quả là một số nguyên là số dư khi ~T~ chia cho ~10^9 + 7~.