Orange Contest #1

Hôm nay, nhân ngày 1/6, bố mẹ cho BabyOrange đi chơi. Thế nhưng, chuyến "đi chơi" thực chất là một chuyến đi tìm kho báu. :)
BabyOrange tuy không biết kho báu ở đâu, nhưng lại biết khoảng cách từ nhà tới chỗ kho báu :)
Nhiệm vụ của bạn là cho \(a\) (km/h) là vận tốc của BabyOrange và \(n\) (km) là khoảng cách từ nhà tới kho báu. Hãy tính thời gian (phút) di chuyển từ nhà tới kho báu của BabyOrange

Input

• Một dòng gồm 2 số \(n\) và \(a\)
• \(0 \le n \le 10^{18}\)
• \(1 \le a \le 10^{18}\)

Output

• Một dòng chứa một số là thời gian di chuyển. Làm tròn đến chữ số thập phân thứ 3.

Example

8 3

160.000

89764565 798653

6743.697

Sau khi tới nơi có kho báu, BabyOrange tưởng rằng họ đã có kho báu nhưng thực chất lại không hề như vậy. Chỉ là một khu rừng hoang sơ với một con đường nhỏ giữa khu rừng. Vì tò mò, họ quyết định đi trên con đường đó. Trên đường, cậu phát hiện có một bức tường chặn giữa đường, giữa bức tường có một cánh cửa bị khóa. Cậu còn phát hiện trên bức tường có khắc một dãy \(N\) con số và một con số \(S\).
Đột nhiên, một dòng chữ trên bức tường bỗng phát sáng: "Muốn bước qua bức tường, cần tìm ra mật mã để mở phong ấn, mật mã chính là tổng số lượng các đoạn liên tiếp trên phiến đã có tổng chia hết cho \(S\)"
Hãy giúp BabyOrange giải mật mã nhé
Lưu ý: Dãy số có thể có số âm 🙂

Input

• Dòng đầu chứa 2 số nguyên \(N\) \((1 \le n \le 200000)\) và \(S\) \((-10^{14} \le S \le 10^{14})\)
• Dòng thứ hai gồm n số nguyên dương \((-10^9 \le {n_i} \le 10^9)\)

Output

• Gồm một số chính là kết quả đề bài

Example

5 3
1 2 -1 4 2

4

8 5
4 1 3 -8 5 -2 7 3

13

Vượt qua cánh cửa, BabyOrange và hoangks7 bước vào một con đường gồm \(n\) viên đá phát sáng. Tuy nhiên, mụ phù thủy liên tục ếm bùa thay đổi "độ nguy hiểm" của con đường. Mụ thực hiện \(Q\) phép thuật. Mỗi phép thuật có thể là cộng thêm độ nguy hiểm vào một đoạn đá từ \(L\) đến \(R\), hoặc yêu cầu họ phải tính tổng độ nguy hiểm từ viên đá \(u\) đến \(v\) để tìm cách bước qua.
Lưu ý: Độ nguy hiểm của \(n\) viên đá lúc đầu đều = 0 và mụ phù thủy có thể giảm độ nguy hiểm nếu \(V\) là số âm

Input

• Dòng đầu gồm \(n\) viên đá và \(Q\) truy vấn \((n, Q \le 2 \times 10^5)\)
• \(Q\) dòng tiếp theo, mỗi dòng có định dạng như sau:
• \(1\) \(L\) \(R\) \(V\): Cộng \(V\) vào đoạn \([L,R]\)
• \(2\) \(u\) \(v\): Tính tổng độ nguy hiểm đoạn \([u,v]\) (modulo \(10^9\) + 7)

Output

• Mỗi lần yêu cầu tính tổng độ nguy hiệm, đưa ra một số là đáp án yêu cầu.

Example

5 4
1 1 3 5
2 2 4
1 3 5 2
2 1 5

10
21

5 8
1 1 5 1000000000
2 2 4
1 2 3 -2000000000
2 1 5
2 2 3
1 3 5 500000005
2 1 4
2 3 5

999999986
1000000000
14
3
500000001

Qua được con đường, BabyOrange và hoangks7 tới một khe nứt vực thẳm. Bắc ngang qua nó là một cây cầu treo dài \(n\) mét. Cả hai người có thể nhảy 1 mét, 2 mét hoặc 3 mét mỗi bước nhảy, và họ đều nhảy cùng lúc. Nhiệm vụ của bạn là tính số cách để họ nhảy qua bên kia. Vì kết quả có thể rất lớn, nên chỉ lấy phần dư khi chia cho \(10^9 + 7\)

Input

• Một dòng duy nhất chứa số \(n\) \((1 \le n \le 10^{18})\)

Output

• Một dòng chứa số cách sau khi chia lấy dư cho \(10^9 + 7\)

Example

3

4

Sau khi băng qua cây cầu treo, BabyOrange và hoangks7 tìm thấy được rương kho báu, mỗi tội... nó bị khóa :(
BabyOrange đột nhiên thấy có gợi ý trên rương, nhờ gợi ý, cả hai người mới biết mật mã là số lượng các "Số Hạnh Phúc" trong khoảng từ \(L\) đến \(R\). Nhiệm vụ của bạn là tìm mật mã cho chiếc rương kho báu đó.
Một số được gọi là "Số Hạnh Phúc" nếu:

• Tổng các chữ số là một số nguyên tố
• Bản thân số đó chia hết cho \(K\)

Input

• Một dòng chứa 3 số nguyên \(L\), \(R\), \(K\)
• \(1 \le L \le R \le 10^{18}\), \(1 \le K \le 100\)

Output

• Một dòng chứa một số là số lượng "Số Hạnh Phúc"

Example

10 20 2

4