Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Một ngày nọ Oppa và Unnie vô tình lạc vào thế giới phép thuật. Người dân ở đây đều có thể sử dụng phép thuật và họ đều rất thân thiện. Ngày Halloween Oppa và Unnie cùng đi dạo quanh N ngôi nhà của dân làng để xin kẹo. Những ngôi nhà này sắp xếp với nhau thành hình tròn để có thể tạo thành kết giới chống lại sức mạnh của những kẻ đến từ vùng đất hắc ám, các ngôi nhà được đánh số từ 1 đến N theo chiều kim đồng hồ và ngôi nhà thứ N sẽ kề với ngôi nhà đầu tiên.

Oppa và Unnie sẽ bắt đầu từ ngôi nhà đầu tiên và đi theo chiều kim đồng hồ, ban đầu chuẩn bị 1 chiếc túi rất lớn (sức chứa tới 10⁹ + 7) với 1 chiếc kẹo ban đầu trong đó, mỗi khi tới nhà một phù thủy thì người phù thủy biết làm 1 trong 2 phép sau:

1. Tăng số kẹo trong túi thêm x cái.
2. Tăng số kẹo trong túi thêm x lần.

Mỗi khi túi đầy thì Oppa sẽ sử dụng chiếc nhẫn không gian của mình để cất và để phần dư còn lại trong túi. Oppa và Unnie đã học được một số phép thuật từ khi tới đây, trong số đó có phép biến hình, tức là hai người sẽ biến hình thành người khác mỗi khi đi quay về ngôi nhà đầu tiên để không ai nhận ra và có thể xin kẹo tiếp, hai người chỉ có đủ lượng mana point đủ để dùng M lần. Hỏi sau khi về nhà trong túi của 2 người sẽ còn bao nhiêu chiếc kẹo.

Input

Dòng đầu tiên gồm 2 số nguyên N, M. (1 ≤ N, M ≤ 10⁵).

N dòng sau mỗi dòng chứa 2 số nguyên k và x (1 ≤ x ≤ 10⁵). k là 1 nếu phù thủy thứ i sẽ dùng phép thứ nhất và bằng 2 nếu là phép thứ 2.

Output

Một số nguyên duy nhất là kết quả của bài toán lấy dư cho 10⁹ + 7.

Example

Input
4 0
1 1
2 2
1 3
2 3

Output
21

Input
4 1
1 1
2 2
1 3
2 3

Output
141