Có bao nhiêu số thập phân, có đúng ~n~ chữ số, có đúng ~k~ chữ số ~X~ và chia hết cho ~3~. Chữ số đứng đầu không phải số ~0~.

Input

Số ~n~, ~k~, và chữ số ~X~

Output

Số lượng số thỏa mãn (số ~0~ không đứng đầu) theo mod ~10^9 + 7~

Giới hạn

• ~X~ là chữ số từ ~0~ đến ~9~.
• ~30\%~ số điểm ~k \leq n \leq 1000~
• ~50\%~ số điểm ~k \leq n \leq 100000~
• ~20\%~ số điểm ~k \leq \min(n, 100000)~, ~n \leq 10^9~

Sample Input

2 1 3

Sample Output

5

Giải thích

Có ~5~ chữ số có ~2~ chữ số, có đúng ~1~ chữ số ~3~ và chia hết cho ~3~, là ~30~, ~36~, ~39~, ~63~, ~93~

Có ~N~ xe trên đường, xe thứ ~i~ đang ở vị trí ~x_i~, di chuyển đều với vận tốc ~v_i~ ~(v_i~ > ~0~ thì xe đi về phía bên phải, ~v_i < 0~ thì xe đi về phía bên trái). Mỗi khi có hai xe thứ ~i~ và thứ ~j~ gặp nhau, 'Điềm' sẽ ghi chép cặp ~(i, j)~ vào quyển sổ của mình. Do đó, quyển sổ của 'Điềm' sẽ được ghi một dãy các cặp ~(i, j)~; trong đó nếu cặp xe ~(i_1~, ~j_1)~ gặp nhau trước cặp ~(i_2, j_2)~ thì cặp ~(i_1, j_1)~ sẽ đứng trước ~(i_2, j_2)~ trong dãy. Hỏi cặp thứ ~K~ trong dãy là cặp nào?

Input

• Dòng ~1~: ~2~ số ~N~, ~K~
• Dòng ~1 + i~: ~2~ số ~x_i~, ~v_i~

Output

~1~ dòng duy nhất có ~2~ số ~i~, ~j~: trong đó ~i < j~ và ~(i, j)~ là cặp số thứ ~K~ trong danh sách của 'Điềm'

Giới hạn

• ~2 \leq N \leq 6.5 \times 10^4~
• ~1 \leq x_i, |v_i| \leq 10^6~
• Không có cặp xe nào thứ tự khác ~K~ mà gặp cùng thời điểm với cặp thứ ~K~.
• ~x_i < xi + 1~
• Luôn tồn tại cặp thứ ~K~

Subtask

• ~30\%~: ~N \leq 10^3~
• ~70\%~: Không có ràng buộc gì thêm

Sample Input 1

4 4
1 9
5 -8
7 3
8 -10

Sample Output 1

1 3

Sample Input 2

8 21
1 8
2 6
3 4
4 1
6 -2
8 -5
9 -8
10 -7

Sample Output 2

3 8

Bạn Thế là một người rất ham học. Bạn ấy rất thích các dãy số, vì vậy bạn luôn muốn được ~a_i~ đó tặng một dãy số nhân dịp sinh nhật.

Đến 290520xx, cậu được chú gà Combi tặng hẳn ~2~ dãy số kèm thiệp chúc mừng trong đó ghi dòng chữ thân thương "Đoán xem". Combi đã tặng Thế ~2~ dãy số ~L~, ~R~ có độ dài ~N \leq 300~ sao cho ~−300 \leq L_i \leq R_i \leq 300~. Thế muốn tạo ra một dãy ~A~ độ dài ~N~ sao cho ~L_i \leq A~ ~i \leq R_i~.

Thế sẽ gửi dạy số đó cho một nhân vật bí ẩn tên là HA. Vì HA rất thích số ~K (|K| \leq 90000)~ nên Thế muốn biết có bao nhiêu cách để làm cho dãy cậu gửi cho HA có tổng dãy con liên tiếp có giá trị lớn nhất đúng bằng ~K~

Input

Dòng đầu ghi ~2~ số ~N~ và ~K~. ~N~ dòng sau, mỗi dòng ghi ~2~ số ~L_i~ và ~R_i~.

Output

Số lượng cách, theo mod ~10^9 + 7~

Subtask

• ~10\%~ số test: ~N \leq 5~, ~|L|, |R| \leq 5~
• ~30\%~ số test: ~N \leq 30~, ~|L|, |R| \leq 30~
• ~60\%~ số test: ~N \leq 300~, ~|L|, |R| \leq 300~

Sample Input

4 2
-3 -3
0 1
-3 3
-4 -3

Sample Output

4

Do tình hình COVID-19 mới xảy ra trong năm nay nên có khá nhiều quốc gia bị ảnh hưởng ở nhiều phương diện (kinh tế, nhân lực, \dots) Do đó, ~n~ ~(n < 2^{15})~ thủ tướng các quốc gia cần tổ chức gấp gáp các cuộc họp quốc tế để cùng nhau giải quyết những vấn đề do bé virus "đáng yêu" nào đó mang lại.

Tuy nhiên, việc trở thành một thủ tướng là một việc vô cùng khó khăn, nên những vị lãnh đạo này thường phải đảm nhận những trọng trách lớn ở tuổi khá cao. Khi đó những cú sốc lớn có thể đến bất cứ lúc nào và khiến các bác đau tim. Do đó, một số thủ tướng cần phải mang theo những dụng cụ cồng kềnh để hỗ trợ ~y~ tế kịp thời (những dụng cụ này cũng chiếm ~1~ chỗ ngồi đó)

Sau cùng, về việc sắp xếp chỗ ngồi của các vị thủ tướng, thứ tự ngồi của họ đã được tính sẵn và chỉ mang tính tương đối (Elizabeth II ngồi trái nhất, Donald Trump ngồi trái thứ hai, Abe Shinzo ngồi trái thứ ba ...).

Tóm lại, mỗi vị lãnh đạo của một quốc gia sẽ chiếm ~1~ - ~2~ chỗ ngồi trong hàng gồm ~m~ ~(m \leq 10^{9})~ ghế xếp ngang của buổi họp ~(1~ chỗ dùng để ngồi và ~1~ chỗ cho dụng cụ trợ tim). Nước sông không phạm nước giếng, tất nhiên ~2~ người khác nhau không ngồi lên đùi nhau, không ngồi lên máy trợ tim của nhau, hay để máy trợ tim đè lên nhau (vì vấn đề kĩ thuật). Và trong trường hợp cần máy trợ tim thì máy trợ tim sẽ luôn được đặt ngay cạnh bên phải của chủ sở hữu. Với những dữ liệu này, bộ phận nhân sự sắp xếp cuộc họp sẽ có bao nhiêu trạng thái khác nhau.

Hai trạng thái được coi là khác nhau khi tồn tại ~1~ vị lãnh đạo có chỗ ngồi khác nhau trong hai trạng thái ~(1~ vị lãnh đạo có thể không tham gia cuộc họp nên với số lượng thủ tướng tham gia nhân sự đều muốn tính kết quả cho kịch bản này).

Input

~2~ số ~m~ và ~n~ ~(m < 10^9~, ~n < 2^{15})~ tương ứng là số ghế và số lãnh đạo tối đa sẽ tham dự.

Output

In ra ~n~ số, với số thứ ~i~ là số trạng thái có thể xảy ra nếu có đúng ~i~ người tham dự. Vì kết quả khá lớn nên kết quả sẽ được lấy modulo ~998244353~

Sample Input 1

3 3

Sample Output 1

5 5 1

Sample Input 2

1 1

Sample Output 2

1

Sample Input 3

5 10

Sample Output 3

9 25 25 9 1 0 0 0 0 0