Cho bảng ~N \times N~ ô vuông. Trong một thao tác, robot có thể lựa chọn ~1~ trong ~4~ cách đi:

• Đi sang phải ~A~ bước.
• Đi sang phải ~B~ bước.
• Đi lên ~C~ bước.
• Đi lên ~D~ bước.

Tìm số thao tác ít nhất để robot đi từ góc dưới trái ~(N, 1)~ lên góc trên phải ~(1, N)~. In ra ~-1~ nếu robot không thể thực hiện được hành trình trên.

Input

Vào từ tệp văn bản ROBOT.INP gồm:

• Dòng đầu gồm một số nguyên ~N~ (~1 \leq N \leq 10^6~).
• Dòng thứ hai gồm hai số ~A~ và ~B~ ~(1\le A,B < N)~.
• Dòng thứ ba gồm hai số ~C~ và ~D~ ~(1\le C,D < N)~.

Output

Đưa ra tệp văn bản ROBOT.OUT một số nguyên là đáp án của bài toán.

Ví dụ

5
2 4
3 4

2

5
2 3
3 4

3

Ràng buộc

1. ~70\%~ số test tương ứng với ~70\%~ số điểm có ~N \leq 10~.
2. ~20\%~ số test khác tương ứng với ~20\%~ số điểm có ~N \leq 10^4~.
3. ~10\%~ số test còn tương ứng với ~10\%~ số điểm không có ràng buộc gì thêm.

Cho dãy số ~a~ độ dài ~n~ chỉ gồm các số nguyên dương không quá ~10^9~ và một số nguyên dương ~k~ (~a_i \leq 10^9,\ k \leq 10^9~).

Một dãy số ~b~ được gọi là dãy con của ~a~ nếu như ~b~ có thể được tạo ra bằng cách xóa đi một vài phần tử liên tiếp ở đầu và cuối dãy số ~a~ (có thể không xóa phần tử nào). Theo định nghĩa này, ~a~ cũng là dãy con của chính nó.

Yêu cầu

Hãy đếm số dãy con của ~a~ sao cho ~sum~, tổng của mọi phần tử trong dãy con đó, không bé hơn ~k~ (~sum \geq k~).

Input

Vào từ tệp văn bản DAYCON.INP gồm:

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~k~ (~1 \leq n \leq 10^6~, ~1 \leq k \leq 10^9~), lần lượt là kích thước dãy số ~a~ và số ~k~ trong mô tả đề bài.

• Dòng thứ hai gồm ~n~ số nguyên dương ~a_i~ (~1 \leq a_i \leq 10^9~), các phần tử của dãy số ~a~.

Output

Đưa ra tệp văn bản DAYCON.OUT một số nguyên không âm duy nhất là số dãy con của ~a~ thỏa điều kiện trên.

Ví dụ

5 6
1 2 1 4 5

6

Ràng buộc

1. ~60\%~ số test tương ứng với ~60\%~ số điểm có ~n \leq 100~.
2. ~30\%~ số test khác tương ứng với ~30\%~ số điểm có ~n \leq 10^3~.
3. ~10\%~ số test còn tương ứng với ~10\%~ số điểm không có ràng buộc gì thêm.

Một số nguyên dương ~x~ được gọi là S-digit nếu như tổng các chữ số của ~x~ là một số nguyên tố. Nhắc lại, số nguyên tố là số nguyên dương có duy nhất hai ước số phân biệt là ~1~ và chính nó (số ~1~ không phải số nguyên tố).

Yêu cầu

Cho ~Q~ truy vấn, mỗi truy vấn có dạng ~l, r~ (~1 \leq l \leq r \leq 250~). Với mỗi truy vấn, đếm số lượng số S-digit có số lượng chữ số không nhỏ hơn ~l~ và không lớn hơn ~r~ (thuộc khoảng ~[l, r]~). Kết quả in ra là phần dư trong phép chia của kết quả tìm được cho ~10^9 + 7~.

Input

Vào từ tệp văn bản SDIGIT.INP gồm:

• Dòng đầu tiên chứa số nguyên dương ~Q~ (~1 \leq Q \leq 10~).
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l~ và ~r~ cách nhau bởi dấu cách, biểu diễn một truy vấn (~1 \leq l \leq r \leq 250~).

Output

Đưa ra tệp văn bản SDIGIT.OUT ~Q~ dòng, mỗi dòng xuất ra một số nguyên. Với truy vấn thứ ~i~, xuất ra phần dư của phép chia giữa kết quả của truy vấn tương ứng và ~10^9 + 7~ trên dòng ~i~.

Ví dụ

2
1 1
1 2

4
37

Ràng buộc

• ~80\%~ số test tương ứng với ~80\%~ số điểm có ~Q \leq 10~ và ~l \leq r \leq 6~.
• ~20\%~ số test còn lại tương ứng với ~20\%~ số điểm có ~Q = 1~ và ~l \leq r \leq 250~.