Hai số nguyên dương ~A~ và ~B~ được gọi là một cặp số tương đồng nếu như chúng có chung tập các ước nguyên tố.

Ví dụ: ~12~ và ~18~ là cặp số tương đồng vì có chung tập ước nguyên tố là ~{2,3}.~

Yêu cầu: Cho trước hai số nguyên dương ~L~ và ~R~, hãy đếm số lượng cặp tương đồng ~A~ và ~B~ mà ~L \le A < B \le R~.

Input

Gồm một dòng duy nhất chứa hai số nguyên dương ~L~ và ~R~ (~L < R \le 10^6~).

Output

Một số nguyên duy nhất là kết quả bài toán.

Scoring

- Có ~60\%~ số test ứng với ~60\%~ số điểm của bài có ~R-L \le 10^3~.

- Có ~40\%~ số test còn lại ứng với ~40\%~ số điểm của bài không giới hạn gì thêm.

Sample Input 1

1 10

Sample Output 1

4

Notes

Có ~4~ cặp số tương đồng đó là: ~2,4~, ~2,8~, ~3,9~, ~4,8~.

Cô An có ~N~ chiếc bánh với ~N~ hương vị khác nhau, có ~N~ học sinh, bạn thứ ~i~ sẽ cảm thấy vui nếu được ăn ~i~ cái bánh.

Yêu cầu: Em hãy đếm có bao nhiêu cách để cô An chia bánh mà có ít nhất 1 bạn cảm thấy vui vẻ.

Input

Gồm 1 dòng duy nhất chứa số nguyên ~N~ (~1 \le N \le 350~).

Output

Ghi ra file văn bản CAKE.OUT là số dư của kết quả khi chia cho ~10^9+7~.

Scoring

- Có ~20\%~ số điểm của bài tương ứng với dữ liệu ~N \le 40~.

- Có ~80\%~ số điểm của bài tương ứng với dữ liệu ~N \le 350~.

Sample Input 1

8

Sample Output 1

9184091

Trong một cánh đồng dài có ~n~ thửa ruộng nằm liền kề nhau. Mỗi thửa ruộng có năng suất thu hoạch lần lượt là ~a_i, a_2, ..., a_n~, trong đó ~a_i~ là số kg lúa thu được trên thửa ruộng thứ ~i~.

Một nông dân muốn thu hoạch một đoạn ruộng liên tiếp để thuận tiện cho việc vận chuyển và đóng gói. Để việc thu hoạch hiệu quả hơn, ông muốn chọn một đoạn gồm ít nhất ~k~ thửa ruộng liên tiếp.

Giả sử người nông dân chọn đoạn ruộng từ thửa ~l~ đến ~r~ (~l \le r~) Khi đó:

- Tổng sản lượng lúa thu được là: ~a_l + a_{l+1} + ... + a_r~.

- Gọi ~g~ là ước số chung lớn nhất (GCD) của các giá trị ~a_l, a_{l+1}, ..., a_r~.

Hiệu quả thu hoạch của đoạn ruộng được định nghĩa là:

Hiệu quả = ~g*(a_l+a_{l+1}+...+a_r)~

Nhiệm vụ của bạn là xác định đoạn ruộng gồm ít nhất ~k~ thửa ruộng liên tiếp sao cho hiệu quả thu hoạch là lớn nhất.

Input

- Dòng thứ nhất chứa hai số nguyên ~n~ và ~k~ (~1 \le k \le n \le 10^6~) - số thửa ruộng và số thửa tối thiểu cần chọn.

- Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^6~) - năng suất thu hoạch của mỗi thửa ruộng.

Output

In ra một số nguyên duy nhất là hiệu quả thu hoạch lớn nhất có thể đạt được.

Scoring

+ ~10\%~ số điểm tương ứng với ~n, k \le 100~.

+ ~20\%~ số điểm tương ứng với ~n, k \le 5*10^3~.

+ ~30\%~ số điểm tương ứng với ~n, k \le 5*10^4~.

+ ~40\%~ số điểm không có ràng buộc thêm.

Sample Input 1

7 2
1 2 1 4 4 4 2

Sample Output 1

48

Mạng lưới giao thông của một quốc gia gồm ~N~ thành phố và ~M~ con đường một chiều. Các thành phố được đánh số từ ~1~ đến ~N~.

Đối với mỗi đường, ta biết:

• Thành phố xuất phát

• Thành phố đích

• Độ dài của con đường

Ta nói rằng đường ~F~ là sự tiếp nối của đường ~E~ nếu thành phố đích của ~E~ trùng với thành phố xuất phát của ~F~.

Một đường đi (path) từ thành phố ~A~ đến thành phố ~B~ là một dãy các con đường thỏa mãn:

• Thành phố xuất phát của con đường đầu tiên là ~A~

• Mỗi con đường tiếp theo là sự tiếp nối của con đường trước đó

• Thành phố đích của con đường cuối cùng là ~B~

Độ dài của đường đi được tính bằng tổng độ dài của tất cả con đường trong đường đi đó. Một đường đi ngắn nhất từ ~A~ đến ~B~ là đường đi mà không tồn tại đường đi nào khác từ ~A~ đến ~B~ có tổng độ dài nhỏ hơn.

Yêu cầu: Đối với mỗi đường, hãy xác định có bao nhiêu đường đi ngắn nhất khác nhau chứa con đường đó. Vì kết quả có thể rất lớn, hãy in kết quả khi chia dư cho ~10^9+7~.

Input

- Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ (~1 \le N \le 1500~, ~1 \le M \le 5*10^3~).

- ~M~ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương ~U~, ~V~ và ~W~. Chúng đại diện cho một con đường một chiều từ thành phố ~U~ đến thành phố ~V~ có độ dài ~W~ (~U \neq V~, ~1 \le U,V \le N~, ~W \le 10^4~).

Output

In ~M~ số nguyên, mỗi số trên một dòng, trong đó:

+ Số thứ ~i~ là số lượng đường đi ngắn nhất khác nhau có chứa con đường thứ ~i~.

+ Kết quả lấy modulo ~10^9+7~.

+ Thứ tự kết quả phải trùng với thứ tự con đường trong dữ liệu vào.

Scoring

- ~30\%~ số điểm tương ứng với ~n \le 15~, ~W \le 30~.

- ~60\%~ số điểm tương ứng với ~n \le 300~, ~W \le 10^3~.

- ~10\%~ số điểm không có ràng buộc gì thêm.

Sample Input 1

4 3
1 2 5
2 3 5
3 4 5

Sample Output 1

3
4
3

Notes

Có ~4~ thành phố và ~3~ con đường:

Đồ thị thực chất là một chuỗi tuyến tính:

~1 \rightarrow 2 \rightarrow 3 \rightarrow 4~

Ta xét mọi cặp thành phố ~(A,B)~ sao cho tồn tại đường đi từ ~A~ đến ~B~.

Các cặp thành phố có đường đi:

Tổng cộng ~6~ đường đi ngắn nhất.

Đếm số đường đi ngắn nhất chứa từng cạnh

Cạnh 1 (~1 \rightarrow 2~) - Các đường đi chứa cạnh này:

~1 \rightarrow 2~

~1 \rightarrow 2 \rightarrow 3~

~1 \rightarrow 2 \rightarrow 3 \rightarrow 4~

~\rightarrow~ Có ~3~ đường.

~\Rightarrow~ Output dòng ~1 = 3~.

Cạnh 2 (~2 \rightarrow 3~) ta làm tương tự.