Cho một dãy số ~A~ gồm ~N~ phần tử ~A_1,A_2,…,A_N~. Một dãy con liên tiếp từ ~L~ đến ~R~ của dãy số ~A~ là các phần tử ~A_L,A_{L+1},…,A_{R-1},A_R~ ~(1≤L≤R≤N)~. Cho một số nguyên dương ~T~, hãy đếm xem có bao dãy con của ~A~ có tổng các phần tử không quá ~T~.

Input:

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~T~ là số lượng phần tử của dãy số ~A~ và số ~T~ cho trước ~(N≤10^6; T≤10^9)~;
• Dòng thứ hai gồm ~N~ số nguyên dương ~A_i~ mô tả các phần tử của dãy số ~A~ ~(1≤i≤N; A_i≤10^9)~.

Output:

Một số nguyên duy nhất là số lượng dãy con thoả mãn yêu cầu đề bài.

Ràng buộc:

• Có 50% số test tương ứng với 50% số điểm có ~N≤100~;
• Có 30% số test khác tương ứng với 30% số điểm có ~N≤5000~;
• 20% số test còn lại tương ứng với 30% số điểm không có ràng buộc gì thêm.

Sample Test 1

Input:

6 8
8 3 2 1 6 9

Output

9

Giải thích

Các dãy con thoả mãn: ~\{8\},\{3\},\{2\},\{1\},\{6\},\{3,2\},\{2,1\},\{1,6\},\{3,2,1\}~

Cho số nguyên dương ~N~. Hãy đếm số cách xoá đi một đoạn chữ số liên tiếp của ~N~ (không được xoá hết) để nhận được số mới chia hết cho ~3~, biết rằng số mới nhận được có thể có thừa chữ số ~0~ ở đầu.

Hai cách xoá được coi là khác nhau nếu có một vị trí được xoá trong cách này nhưng không được xoá trong cách kia.

Input

• Gồm một dòng duy nhất chứa một số nguyên ~N~ (~1 \le N \le 10^{100000}~).

Output

• In ra một số nguyên là số cách xoá tìm được.

Subtasks

• Subtask 1 (~50\%~ số điểm): ~N \le 10^{300}~.
• Subtask 2 (~25\%~ số điểm): ~N \le 10^{10000}~.
• Subtask 3 (~25\%~ số điểm): Không có ràng buộc gì thêm.

Sample Test 1

Input

1005

Output

4

Sample Test 2

Input

2009

Output

3

Cho số ~n~ và dãy số nguyên ~a~ gồm ~n~ phần tử, hãy tìm đoạn con liên tiếp dài nhất của dãy ~a~ có trung bình cộng lớn hơn hoặc bằng ~k~ cho trước.

Input

• Dòng đầu gồm 2 số nguyên ~n~ ~(1 \le n \le 10^5)~ và ~k~ ~(|k| \le 10^6)~.
• Dòng sau gồm ~n~ số nguyên miêu tả dãy ~a~ ~(|a_i| \le 10^6)~

Output

• In ra một số nguyên là độ dài của dãy con liên tiếp dài nhất thỏa mãn.

Sample Test

Input

7 3
1 5 2 3 1 4 1

Output

5

Cho một dãy số ~A~ nguyên không âm gồm ~n~ phần tử và một số ~k~ bất kì ~(k<=n)~. Ta định nghĩa ý nghĩa của dãy số này chính bằng trung bình cộng lớn nhất của một đoạn con liên tiếp bất kì trong dãy với độ dài lớn hơn hoặc bằng ~k~. Nói cách khác, ý nghĩa của dãy chính bằng ~max(f(l,r))~, với ~f(l,r)~ là trung bình cộng của đoạn con ~[l,r]~ và ~(1 \le l \le r \le n, r-l+1 \ge k)~. Hãy lập trình để đi tìm ý nghĩa của dãy.

Input:

• Dòng đầu gồm 3 số ~n,k,h~.
• Dòng sau là ~n~ phần tử của dãy ~A~. (~1 \le k \le n \le 10^5, 0 \le h \le 1~), (~A_i \le 10^5 ~ với mọi ~1 \le i \le n~).

Output:

Nếu ~h = 0~, in ra phần nguyên của kết quả tìm được. Ngược lại nếu ~h = 1~, in ra kết quả lấy 3 chữ số thập phân sau dấu phẩy.

Sample Test 1

Input:

4 2 0 
17 0 14 1

Output:

10

Sample Test 2

Input:

4 2 1
17 0 14 1

Output:

10.333

Giải thích:

• Ở test 1, đoạn con thỏa mãn là ~[1,3]~ có giá trị trung bình là 10.(333). Tuy nhiên do ~h = 0~ nên ta chỉ lấy phần nguyên của kết quả là 10.
• Ở test 2, tương tự test 1, nhưng do ~h = 1~ nên ta lấy kết quả = 10.333

Ràng buộc

• Subtask 1: ~n \le 1000~. (50%)
• Subtask 2: ~n \le 10^5, h = 0~. (30%)
• Subtask 3: ~n \le 10^5~. (20%)

Cho hai số ~n, k~ và dãy số nguyên ~a~ gồm ~n~ phần tử, hãy tìm đoạn con liên tiếp có độ dài không lớn hơn ~k~ của dãy ~a~ có trung bình cộng lớn nhất.

Input

• Dòng đầu gồm 2 số nguyên ~n, k~ ~(1 < k \le n \le 2*10^5)~;
• Dòng sau gồm ~n~ số nguyên mô tả dãy ~a~ ~(|a_i| \le 10^9)~.

Output

• In ra một số thực duy nhất là giá trị trung bình cộng lớn nhất thỏa mãn. Kết quả lấy ~3~ chữ số sau dấu phẩy.

Sample Test

Input

4 3
17 0 14 1

Output

10.333

Mít có các que tính có nhiều độ dài và màu sắc. Hôm nay học về hình tam giác nhọn, Mít đã nghĩ ra một bài toán rất độc đáo có liên quan tới tam giác nhọn và các que tính của mình. Mít chia các que tính thành ~N~ bộ, các que tính trong cùng một bộ thì có độ dài bằng nhau nhưng có màu khác nhau. Độ dài của các que tính trong hai bộ bất kì là khác nhau. Mít đố các bạn đếm xem có bao nhiêu tam giác nhọn khác nhau có thể được tạo ra từ ~N~ bộ que tính đó. Chú ý: mỗi cạnh của tam giác được chọn từ một bộ que tính khác nhau tức là sẽ không có tam giác cân và hai tam giác nhọn được gọi là giống nhau khi các cặp cạnh tương ứng bằng nhau và cùng màu, ngược lại là khác nhau.

Yêu cầu: Cho độ dài và số lượng các que tính của ~N~ bộ que tính, hãy lập trình đếm số lượng tam giác nhọn khác nhau có thể tạo ra.

Dữ liệu vào từ tệp văn bản TRIACU.INP:

• Dòng đầu tiên gồm một số nguyên dương ~N~ ~(N ≤ 2000)~ là số bộ que tính;
• ~N~ dòng sau, dòng thứ ~i~ chứa hai số nguyên dương ~L, C~ mô tả độ dài và số lượng que tính của bộ thứ ~i~ ~(1 ≤ i ≤ N~; ~\ L ≤ 10^6~; ~\ C ≤ 10^3)~.

Kết quả ghi ra tệp văn bản TRIACU.OUT:

Một số nguyên duy nhất là số lượng tam giác nhọn khác nhau.

Ràng buộc

• Có ~50\%~ số test ứng với ~N ≤ 200~;
• ~50\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input

4
3 3
4 1
5 2
6 2

Output

4

Giải thích

Có ~4~ tam giác nhọn có thể tạo ra từ bộ que tính thứ ~2, 3, 4~.

Dino đang học về các con số. Bố cho Dino ~a_0~ chữ số ~0~; ~a_1~ chữ số ~1~; ...; ~a_9~ chữ số ~9~. Bố hỏi Dino có thể ghép được nhiều nhất bao nhiêu số tự nhiên liên tiếp từ ~N~ trở đi. Bạn hãy lập trình giúp Dino kiểm tra xem.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(N \le 10^9)~;
• Dòng thứ hai chứa 10 số nguyên mô tả số lượng các chữ số từ ~0~ đến ~9~: ~a_0, a_1, ..., a_9~ ~(0 \le a_i \le 10^{11})~.

  Output

Số lượng số mà Dino ghép được nhiều nhất thoả mãn đề bài.

Sample Test 1

Input

12
0 4 2 1 1 1 3 0 0 0

Output

4

Giải thích: Ghép được thành ~4~ số: ~12, 13, 14, 15~. Không ghép được thành ~16~ vì không đủ chữ số ~1~.

Sample Test 2

Input

103
9 4 2 0 1 1 3 0 0 0

Output

0

Có ~n~ người xếp hàng mua vé một trận bóng theo thứ tự ~1~ đến ~n~. Mỗi người cần mua một vé, nhưng người bán vé lại có thể bán cho mỗi người tối đa hai vé. Do đó, một số người có thể rời hàng và nhờ người đứng trước mình mua hộ vé. Biết ~t_i~ là thời gian cần thiết để người thứ ~i~ mua vé cho mình. Nếu người thứ ~i+1~ rời hàng và nhờ người ~i~ mua hộ vé thì mất ~r_i~ thời gian để mua cho cả hai.

Hãy xác định thời gian mua vé nhỏ nhất.

Input

• Dòng đầu chứa số nguyên dương ~n~ ~(n \le 6*10^4)~
• Dòng thứ hai chứa ~n~ số nguyên dương miêu tả dãy ~t[1], t[2], ..., t[n]~.~(t[i] \le 30000)~
• Dòng thứ ba chứa ~n-1~ số nguyên dương miêu tả dãy ~r_[1], r_[2], ..., r_[n-1]~. ~(r[i] \le 30000)~

Output

• In ra thời gian ít nhất để mua vé cho ~n~ người.

Sample Test

Input

5
2 5 7 8 4
4 9 10 10

Output

18

Alice Margatroid cần dọn tuyết trên mái nhà. Cô sẽ dùng chọn ra ~m~ con búp bê của mình để thực hiện nhiệm vụ. Alice có ~n~ thùng đựng búp bê, thùng thứ ~i~ có ~a_i~ con, và cô muốn mỗi thùng chỉ được chọn ra tối đa 1 con búp bê. Hỏi có bao nhiêu cách để chọn ra ~m~ con búp bê.

Input

• Dòng đầu tiên gồm 2 số tự nhiên ~n, m~ ~(1 \le m \le n \le 1000)~
• Dòng tiếp theo gồm ~n~ số tự nhiên là số lượng búp bê của từng thùng. (~1 \le a[i] \le 10^9~)

Output

• Gồm 1 số tự nhiên duy nhất là số cách chọn búp bê modulo ~10^9 + 7~

Sample Test

Input:

3 2
1 2 1

Output:

5

Giải thích:

• Có 5 cách chọn là: ~\{1, 2.1\}, \{1, 2.2\}, \{1, 3\}, \{2.1, 3\}, \{2.2, 3\}~ với ~x.y~ là con búp bê thứ ~y~ của thùng thứ ~x~

Một xâu ~S~ được gọi là xâu đối xứng nếu ~S = S'~ với ~S'~ là xâu nhận được từ xâu ~S~ khi đọc từ phải qua trái. Ví dụ: Xâu ~'aba'~ là xâu đối xứng, còn xâu ~'abc'~ là xâu không đối xứng.

Cho một xâu ~S~ gồm ~1 \le n \le 1000~ kí tự.

Yêu cầu: Hãy tìm cách chia xâu ~S~ thành ít nhất các đoạn mà mỗi đoạn đều là các xâu đối xứng.

Input

• Dòng đầu gồm một số nguyên ~n~ là độ dài của xâu ~S~.
• Dòng thứ hai là nội dung xâu ~S~.

Output

• Dòng đầu ghi một số nguyên ~k~ (số đoạn ít nhất tìm được).
• ~K~ dòng sau, mỗi dòng ghi một số nguyên ~t_i~, với ~t_i~ là vị trí kết thúc của đoạn thứ ~i~.

Sample Input 1

 8
 abbacdcb

Sample Output 1

3
4
7
8

Hôm nay Kaku Seiga đến Nhân Thôn để đi ăn trộm. Có ~n~ ngôi nhà ở cạnh nhau. Số tiền trong ngôi nhà thứ ~i~ là ~a_i~. Cô sẽ không vào ~k~ nhà liên tiếp trở lên vì sẽ rất dễ bị phát hiện. Hãy cho cô biết cô sẽ lấy được số tiền lớn nhất là bao nhiêu?

Input:

• Dòng đầu gồm 2 số nguyên dương ~n~ và ~k~.
• Dòng sau gồm ~n~ số nguyên dương miêu tả dãy ~a~.

Output:

• Số tiền lớn nhất Seiga có thể lấy được

Sample Test

Input:

6 3
6 10 10 13 10 10

Output:

40

Giải thích:

• Chọn các số 2 3 5 6.

Giới hạn:

• ~1 \le k \le n \le 10^5, 1 \le a_i \le 10^6~

Cho dãy gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~ chỉ gồm các số ~1~, ~2~ và ~3~. Đếm số cách xoá một vài phần tử của dãy (có thể không xoá) để nhận được một dãy thoả mãn hai yêu cầu sau:

1. Dãy còn ít nhất ~3~ phần tử
2. Phần tử đầu tiên của dãy có giá trị ~1~, tiếp theo là một số phần tử có giá trị ~2~ (ít nhất một số ~2~), kết thúc bằng đúng một phần tử có giá trị ~3~.

Ví dụ: các dãy ~\{1, 2, 2, 3\}~ và dãy ~\{1, 2, 3\}~ thoả mãn yêu cầu, các dãy ~\{1, 2, 3, 3\}~ và dãy ~\{1, 1, 2, 3\}~ không thoả mãn yêu cầu.

Vì số cách xoá có thể rất lớn, hãy in ra số cách xoá chia lấy dư cho ~10^9+7~.

Input

Dòng đầu chứa số nguyên ~n~ (~1 \le n \le 10^6~) là số lượng phần tử của dãy.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 3~) mô tả các phần tử của dãy.

Output

Gồm một dòng duy nhất chứa một số nguyên là số cách xoá thoả mãn yêu cầu đề bài, chia lấy dư cho ~10^9+7~.

Example

Input

8
1 2 1 2 3 1 2 3

Output

15

Gọi ~A~ là dãy số với ~A(i)~ được tạo bởi ghép ~i~ số nguyên tố đầu tiên với nhau: ~2, 23, 235, 2357, 235711, 23571113, ... ~.

Cho ~n~ và ~k~, hãy tìm cách xóa ~k~ chữ số ra khỏi số ~A(n)~ để thu được số lớn nhất có thể.

Input

• Gồm một dòng chứa hai số nguyên không âm ~n~ và ~k~ ~(1 \le n \le 50000)~, dữ liệu đảm bảo ~k~ bé hơn số chữ số của ~A(n)~.

  Output

• In ra một dòng miêu tả kết quả của bài toán.

Subtask

• ~50\%~ số test có ~n \le 50~.
• ~50\%~ số test không ràng buộc gì thêm.

Sample Input 1:

7 4

Sample Output 1:

711317

Cho một dãy ~a~ gồm ~n~ phần tử phân biệt. Ta định nghĩa hàm ~g(l,r)~ như sau:

• ~g(l,r) = Max(l,r) \oplus MaxSecond(l,r)~. Ở đây, ~\oplus~ là toán tử ~xor~.
• Trong đó ~Max(l,r)~ là số lớn nhất trong đoạn ~[l,r]~, ~MaxSecond(l,r)~ là số lớn thứ hai trong đoạn ~[l,r]~.

Hãy tính ~max(g(l,r))~ với mọi đoạn ~[l,r]~ của dãy ~a~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~. ~(1 \le n \le 10^5).~
• Dòng sau gồm ~n~ số nguyên dương miêu tả dãy ~a~. ~(1 \le a[i] \le 10^9~ ~\forall (1 \le i \le n))~.

Output

• In ra một dòng miêu tả kết quả của bài toán.

Subtask

• ~50\%~ số test có ~n \le 1000~.
• ~50\%~ còn lại không có điều kiện gì thêm.

Sample Input 1:

5
5 2 1 4 3

Sample Output 1:

7

Explanation 1:

• Kết quả chính là ~g(4,5) = 4 \oplus 3 = 7~, hoặc ~g(1,2)~.

Sample Input 2:

5
9 8 3 5 7

Sample Output 2:

15

Explanation 2:

• Kết quả là ~g(2,5)~.