Nhiệm vụ của bạn là phải tạo ra một tổng ~n~ bằng cách tung xúc xắc một hoặc nhiều lần. Mỗi lần tung sẽ cho ra một số nguyên trong khoảng ~1~ đến ~6~.

Ví dụ, nếu ~n = 3~ thì sẽ có 4 cách:

• ~1 + 1 + 1~
• ~1 + 2~
• ~2 + 1~
• ~3~

Input

• Dòng duy nhất chứa số nguyên ~n~ (~1 \leq n \leq 10^6~)

Output

• In ra số cách tung xúc xắc, lấy phần dư khi chia cho ~10^9 + 7~.

Sample Test

Bạn được cho một mảng gồm ~n~ số nguyên. Nhiệm vụ của bạn là tính toán trung vị của mỗi đoạn con gồm ~k~ phần tử liên tiếp, từ trái sang phải.

Trung vị là phần tử ở giữa khi các phần tử được sắp xếp. Nếu số lượng phần tử là số chẵn, có thể có hai trung vị và chúng ta giả định rằng trung vị là số nhỏ hơn trong chúng.

Input

• Dòng đầu vào đầu tiên chứa hai số nguyên ~n~ và ~k~: số lượng phần tử và kích thước của đoạn con.
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ - nội dung của mảng.

Output

• In ra ~n - k + 1~ giá trị: các trung vị

Constraints

• ~1 \leq k \leq n \leq 2 \times 10^5~
• ~1 \leq a_i \leq 10^9~.

Sample Test

Input:

8 3
2 4 3 5 8 1 2 1

Output:

3 4 5 5 2 1