Các bạn bò đã thành lập 1 đội nhảy mới!!! Bác nông dân John được may mắn trở thành biên đạo của đội nhảy thế kỉ này. Điệu nhảy tuyệt vời nhất của đội bao gồm \(N\) bạn bò đứng thành 1 hàng \((1 \leq N \leq 10^6)\). Ở mỗi bước nhảy, 2 bạn bò cách nhau \(K\) vị trí \((1 \leq K < N)\) nhẹ nhàng nhảy lên và đáp xuống ở vị trí của bạn còn lại.

Mỗi bạn bò lại thuộc \(1\) trong \(2\) gia tộc bò khác nhau - nhà Guernseys và nhà Holsteins. Biên đạo John đã ghi chép lại điệu nhảy bằng \(1\) dãy các chuỗi nhị phân độ dài \(N\) với \(0\) là biểu diễn cho bạn bò nhà Guernseys, \(1\) là biểu diễn cho bạn bò nhà Holsteins, và các chuỗi nhị phân cho biết các bạn bò sẽ được sắp xếp như thế nào trong suốt điệu nhảy.

Nhưng không may thay, tên nông dân Nhoj xấu xa (biên đạo của đội nhảy đối thủ) đã đột nhập vào và xoá đi tất cả chuỗi nhị phân của John trừ chuỗi đầu tiên và cuối cùng! Một cuộc thi lớn đang sắp sửa diễn ra, bác đạo John không được phép tốn thêm thời gian để xây dựng lại các chuỗi nhị phân nữa.

Vì vậy, bác John đưa cho bạn \(2\) chuỗi nhị phân này, bạn hãy giúp bác tìm ra số bước nhảy ít nhất có thể để các bạn bò bắt đầu sắp xếp theo chuỗi nhị phân đầu tiên khi điều nhảy bắt đầu và theo chuỗi nhị phân cuối khi điệu nhảy kết thúc nhé!

Input

• Dòng đầu tiên gồm \(2\) số \(N\) và \(K\).
• Dòng thứ hai gồm chuỗi nhị phân đầu tiên.
• Dòng thứ ba gồm chuỗi nhị phân cuối cùng.

Output

• Số bước nhảy ít nhất có thể đạt được.

Scoring

• Subtask \(1\): \(K = 1\).
• Subtask \(2\): Có ít nhất \(8\) bạn bò đền từ nhà Vastaya.
• Subtask \(3\): \(N \leq 5000\).
• Subtask \(4\): Không có ràng buộc gì thêm.

Example

4 1
0111
1110

3

5 4
11000
00011

2

Cô bò Bessie đang trồng cỏ trên một đường thẳng. Nàng bò nhà ta có \(N\) \((1 \leq N \leq 2 * 10^5)\) giống cỏ khác nhau, giống cỏ \(i\) sẽ được trồng trên đoạn \([l_i, r_i]\) \((0 < l_i < r_i \leq 10^9)\).

Thêm nữa, giống cỏ \(i\) còn tăng trưởng tốt hơn khi có một số giống cỏ \(j\) \((j \ne i)\) nào đó mà giống cỏ \(i\) và \(j\) cùng được trồng trên \(1\) đoạn giao nhau với độ dài tối thiểu là \(k_i\) \((0 < k_i \leq r_i - l_i)\). Bessie muốn phỏng đoán sự tăng trưởng của các giống này, vì thế nên với mỗi giống cỏ \(i\), cô nàng muốn biết có bao nhiêu giống cỏ \(j \ne i\) mà giống cỏ \(j\) và \(i\) cùng được trồng trên \(1\) đoạn giao nhau với độ dài không bé hơn \(k_i\) nhé!

Input

• Dòng đầu tiên chứa số nguyên \(N\).
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(3\) số nguyên dương \(l_i\), \(r_i\) và \(k_i\).

Output

• Gồm \(N\) dòng, trong đó dòng thứ \(i\) là đáp án của giống cỏ \(i\).

Scoring

• Subtask \(1\): \(N \leq 5000\).
• Subtask \(2\): \(k_i\) giống nhau \(\forall i \in [1, N]\).
• Subtask \(3\): Không có ràng buộc gì thêm.

Example

2
3 6 3
4 7 2

0
1

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

3
3
2
2

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

0
3
1
3
3

Lần này, nàng bò Bessie của chúng ta có hai dãy số độ dài \(N\) \((1 \leq N \leq 500)\) là \(a\) và \(b\) \((1 \leq a_i, b_i \leq 10^6)\).

Bessie muốn chia cả hai dãy này thành các dãy con không rỗng sao cho:

• Mỗi phần tử thuộc vào đúng \(1\) dãy con.
• Hai dãy đều có cùng số lượng dãy con. Gọi số lượng dãy con này là \(k\), các dãy con được đánh số từ \(1\) đến \(k\) từ trái sang phải.
• Với mỗi dãy con \(1 \leq i \leq k\), trung bình cộng của dãy con \(i\) trên dãy \(a\) không lớn hơn trung bình cộng của dãy con \(i\) trên dãy \(b\).

Hãy đếm số cách mà Bessie có thể chia cả hai dãy thành các dãy con không rỗng thoả mãn điều kiện trên, lấy phần dư khi chia cho \(10^9 + 7\). Hai cách chia được gọi là khác nhau nếu số lượng dãy con khác nhau hoặc có một số phần tử thuộc dãy con \(i\) nào đó trong một cách chia và không thuộc dãy con \(i\) trong cách chia còn lại.

Input

• Dòng đầu tiên chứa số \(N\).
• Dòng thứ hai gồm \(N\) số \(a_1, a_2, ..., a_n\).
• Dòng thứ ba gồm \(N\) số \(b_1, b_2, ..., b_n\).

Output

• Số cách chia dãy con lấy phần dư khi chia cho \(10^9 + 7\).

Scoring

• Subtask \(1\): \(N \leq 10\)
• Subtask \(2\): \(N \leq 80\)
• Subtask \(3\): \(N \leq 300\)
• Subtask \(4\): \(N \leq 500\)

Example

2
1 2
2 2

2

3
1 3 2
2 2 2

3

5
2 5 1 3 2
2 1 5 2 2

1