Một đất nước có ~N~ thành phố, mỗi thành phố được đặc trưng bởi ~2~ con số: ~A_i~ và ~B_i~ (trong đó: ~A_i~ là khả năng tăng trưởng của thành phố đó và ~B_i~ là "chỉ số ngôn ngữ" của thành phố đó). Một "liên minh" là ~1~ tập hợp gồm ~k~ thành phố trong ~N~ thành phố của đất nước (~k \le N~) và có ít nhất ~2~ thành phố khác nhau về chỉ số ngôn ngữ. "Khả năng liên minh" của ~k~ thành phố trong ~1~ liên minh được tính bằng tích các khả năng tăng trưởng của ~k~ thành phố đó. Khả năng tăng trưởng của đất nước sẽ được tính bằng tổng tất cả các khả năng liên minh của các liên minh, và tất cả các liên minh này đều khác nhau.

Ví dụ ~1~ liên minh gồm ~5~ thành phố là: ~1~, ~4~, ~2~, ~5~, ~6~ thì khả năng liên minh sẽ là ~A_1*A_4*A_2*A_5*A_6~.

Hai liên minh được gọi là khác nhau nếu tồn tại "ít nhất" một thành phố có trong liên mình này mà không có trong liên minh kia.

Input

Dòng đầu gồm ~2~ số ~n~ và ~k~ (~2 \le n \le 10^5~, ~2 \le k \le 50~)

~N~ dòng tiếp theo: mỗi dòng gồm ~2~ số ~A_i~ và ~B_i~ (~A_i \le 1000~ và ~B_i \le~ 10 ~^9~)

Output

Gồm ~1~ dòng duy nhất: Khả năng tăng trưởng của đất nước theo module ~790972~.

Sample Input

5 3
4 1
6 4
5 3
2 2
3 5

Sample Output

580