Bạn đang chơi một trò chơi nhỏ tên là “Loại bỏ đá”.

Có $n$ đống đá xếp thành một hàng, đống thứ $i$ có $a_i$ viên. Nhiệm vụ của bạn là loại bỏ toàn bộ đá bằng các thao tác sau:

• Thao tác một: Chọn một đống đá và loại bỏ ít nhất $2$ viên trong đống đó;
• Thao tác hai: Chọn một đoạn số hiệu liên tiếp $[l,r]$ ($1\le l\le r\le n$) thỏa mãn $r-l\ge2$, rồi loại bỏ đúng $1$ viên ở mỗi đống trong đoạn.

Bạn có thể thực hiện hai loại thao tác trên bao nhiêu lần tùy ý và theo thứ tự bất kỳ cho đến khi không thể thực hiện tiếp. Bạn thắng nếu cuối cùng loại bỏ được toàn bộ đá.

Có lẽ bạn đã bắt đầu tính những vấn đề như “có bao nhiêu cách thao tác khác nhau về bản chất”, nhưng khi chơi thực tế lại thấy mình luôn thua. Vì vậy, bạn định dùng một mẹo nhỏ: lúc bắt đầu, bạn giấu sẵn $k$ viên đá trong tay. Trước khi thực hiện bất kỳ thao tác nào, bạn có thể và bắt buộc phải bỏ toàn bộ số đá này vào một hoặc nhiều đống. Bạn hy vọng điều này tăng khả năng thắng, nhưng cũng hiểu nó có thể khiến bạn thua một ván vốn có thể thắng.

Giờ đây, bạn được tự chọn trạng thái ban đầu. Cụ thể, mỗi $a_i$ có thể là một số nguyên bất kỳ trong $[l_i,r_i]$. Bạn muốn đếm số trạng thái ban đầu mà bạn có ít nhất một cách thắng. Vì đáp án rất lớn, chỉ cần in ra kết quả modulo $10^9+7$. Hai trạng thái ban đầu khác nhau khi và chỉ khi tồn tại ít nhất một $1\le i\le n$ mà giá trị $a_i$ khác nhau. Lưu ý “trạng thái ban đầu” ở đây là trạng thái trước khi bạn thêm $k$ viên đá.

Dữ liệu vào

Đọc dữ liệu từ tệp stone.in.

Bài có nhiều bộ dữ liệu kiểm thử. Dòng đầu tiên chứa số nguyên dương $T$ là số bộ dữ liệu, tiếp theo lần lượt là các bộ dữ liệu.

Với mỗi bộ dữ liệu, dòng đầu tiên chứa hai số nguyên $n,k$, lần lượt là số đống đá và số viên đá được thêm. Trong $n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên không âm $l_i,r_i$, là phạm vi số đá ban đầu của mỗi đống.

Dữ liệu ra

Ghi kết quả vào tệp stone.out.

Với mỗi bộ dữ liệu, in ra một số nguyên trên một dòng, là số trạng thái có thể thắng modulo $10^9+7$.

Ví dụ

Dữ liệu vào 1

1
4 1
0 1
0 1
0 1
0 1

Dữ liệu ra 1

14

Ghi chú

Có $2^4=16$ trạng thái ban đầu có thể có. Có thể chứng minh rằng ngoài hai trạng thái $(0\ 0\ 0\ 0)$ và $(1\ 0\ 0\ 1)$ không thể thắng, mọi trạng thái còn lại đều có cách thắng. Ví dụ, với trạng thái ban đầu $(1\ 0\ 1\ 0)$, bạn có thể bỏ $1$ viên đá trong tay vào đống thứ $2$, khiến trạng thái trở thành $(1\ 1\ 1\ 0)$, rồi dùng thao tác hai một lần trên đoạn $[1,3]$.

Ví dụ 2

Xem các tệp stone/stone2.in và stone/stone2.ans trong thư mục của thí sinh.

Ví dụ 3

Xem các tệp stone/stone3.in và stone/stone3.ans trong thư mục của thí sinh.

Ví dụ 4

Xem các tệp stone/stone4.in và stone/stone4.ans trong thư mục của thí sinh.

Giới hạn

Với $100\%$ dữ liệu, bảo đảm $T\le10$, $3\le n\le1000$, $0\le l_i\le r_i\le10^9$, $0\le k\le100$.