Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P193PROE - Problem E - Xin kẹo

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 109 + 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 ≤ 105).

N dòng sau mỗi dòng chứa 2 số nguyên k và x (1 ≤ x ≤ 105). 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 109 + 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

Được gửi lên bởi:adm
Ngày:2019-03-01
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.