Pokemon - PhuocThien (Div. 02)

Ánh nắng ban mai rực rỡ len lỏi qua từng tán lá rậm rạp của khu rừng Viridian Forest, đánh thức muôn loài sinh vật kỳ bí đang say giấc nồng, đồng thời cũng chính thức mở ra chương đầu tiên trong chuyến hành trình vĩ đại của Ash và người bạn đồng hành thân thiết Pikachu. Khu rừng này từ lâu đã được giới đạo tặc Team Rocket và các nhà thám hiểm truyền tai nhau về một cấu trúc địa lý vô cùng kỳ lạ và phức tạp, không giống với bất kỳ hệ sinh thái nào trên thế giới. Theo những ghi chép cổ xưa mà Professor Oak đã dày công nghiên cứu và trao lại cho Ash, khu rừng không phải là một mặt phẳng thông thường mà được chia thành \(n\) bãi cỏ biệt lập. Những bãi cỏ này được kết nối với nhau bởi chính xác \(n-1\) con đường mòn phủ đầy rêu xanh và lá khô, tạo thành một hệ thống mạng lưới hoàn hảo sao cho từ một bãi cỏ bất kỳ, người ta luôn có thể tìm được đường đi đến mọi bãi cỏ khác mà không bị chia cắt, một cấu trúc mà các nhà toán học gọi là "cây".

Tại mỗi bãi cỏ thứ \(i\), hệ thống radar trên chiếc máy Pokedex thế hệ mới của Ash liên tục phát ra tiếng bíp bíp, quét được sự hiện diện của một chú Pokemon hoang dã mang trong mình mức năng lượng chiến đấu tiềm tàng là \(a_i\). Với ngọn lửa nhiệt huyết rực cháy trong tim và khát khao thu thập những người bạn đồng hành mạnh mẽ nhất, Ash quyết tâm thu phục một đội hình Pokemon từ khu rừng này sao cho tổng mức năng lượng chiến đấu của toàn đội đạt đến ngưỡng vĩ đại nhất có thể. Tuy nhiên, mẹ thiên nhiên luôn có những quy luật khắc nghiệt của riêng mình: các loài Pokemon sống ở hai bãi cỏ kề nhau (tức là có một con đường mòn nối trực tiếp giữa chúng) thường có tập tính bảo vệ lãnh thổ cực kỳ cao và coi nhau như những kẻ thù không đội trời chung. Nếu Ash vô tình thu phục cả hai Pokemon ở hai bãi cỏ kề nhau này, chúng sẽ mang theo sự thù hằn vào bên trong những quả Pokeball, lập tức lao vào cắn xé và đánh nhau loạn xạ, gây ra sự hỗn loạn tột độ và có nguy cơ phá hủy hoàn toàn đội hình mà cậu đang cất công xây dựng.

Nhận thức được mối nguy hiểm tiềm tàng này, Ash tự đặt ra một quy tắc sinh tử: tuyệt đối không bao giờ được phép thu phục hai Pokemon ở hai bãi cỏ có đường nối trực tiếp với nhau. Đứng trước một hệ sinh thái đan xen phức tạp cùng hàng vạn ngã rẽ của tự nhiên, Ash đang thực sự đau đầu trong việc lựa chọn mục tiêu. Bằng tất cả kiến thức về quy hoạch động trên cây mà bạn đã rèn luyện, hãy giúp Ash tính toán một chiến thuật hoàn hảo xem tổng mức năng lượng chiến đấu lớn nhất mà cậu có thể thu phục được một cách an toàn tuyệt đối là bao nhiêu, để cậu có thể tự tin bước tiếp trên con đường trở thành Pokemon Master.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 10^5\)) — số lượng bãi cỏ trong Viridian Forest.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)) — mức năng lượng chiến đấu của Pokemon tại bãi cỏ thứ \(i\).
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) (\(1 \le u, v \le n\)) mô tả một con đường mòn nối trực tiếp giữa bãi cỏ \(u\) và bãi cỏ \(v\).

Output

• In ra một số nguyên duy nhất là tổng mức năng lượng lớn nhất có thể thu phục mà không vi phạm quy tắc lãnh thổ.

Example

3
10 20 30
1 2
2 3

40

5
50 10 10 10 10
1 2
1 3
1 4
1 5

50

7
1 2 3 4 5 6 7
1 2
1 3
2 4
2 5
3 6
3 7

23

Scoring

• Subtask \(1\) (\(20\%\) điểm): \(1 \le n \le 20\).
• Subtask \(2\) (\(30\%\) điểm): \(1 \le n \le 2000\).
• Subtask \(3\) (\(50\%\) điểm): Không còn ràng buộc gì thêm.

Sau khi rời khỏi khu rừng rậm rạp với một đội hình Pokemon ưng ý, bầu trời đột ngột tối sầm lại, những đám mây đen kịt cuồn cuộn kéo đến mang theo sấm chớp rền vang, báo hiệu một cơn bão kinh hoàng sắp sửa trút xuống. Để bảo vệ những người bạn nhỏ của mình, Ash và Pikachu buộc phải chạy thục mạng tìm nơi trú ẩn và vô tình bước chân vào Hang Động Sấm Sét, một nơi tối tăm, ẩm thấp và chứa đựng vô vàn những truyền thuyết đáng sợ. Tương truyền rằng, sâu thẳm bên dưới tầng địa chất của hang động này chính là nơi an nghỉ và phục hồi năng lượng của Zapdos - một trong ba con chim huyền thoại mang sức mạnh chi phối sấm sét của tự nhiên.

Theo bản đồ ba chiều mà Pokedex vừa quét được, cấu trúc bên trong của hang động giống hệt như một ma trận lưới khổng lồ bao gồm \(M\) hàng và \(N\) cột trải dài tít tắp. Ban đầu, do sự hỗn loạn lúc chạy trốn cơn bão, Ash bị đẩy vào đứng ở ô tọa độ \((1, 1)\) nằm tận cùng góc trên bên trái của hang, và mục tiêu sinh tử của cậu lúc này là phải tìm đường di chuyển đến lối ra duy nhất nằm ở ô \((M, N)\) tại góc dưới cùng bên phải để hy vọng có cơ hội diện kiến Zapdos. Không may thay, địa hình trong hang vô cùng dốc và trơn trượt bởi những dòng nước ngầm rỉ ra từ vách đá, khiến cho ở mỗi bước đi, cậu chỉ có thể cẩn thận bước chân xuống dưới một ô hoặc di chuyển sang phải một ô để giữ thăng bằng.

Hang động này không hề yên bình; rải rác khắp các lối đi là những tinh thể điện từ phát sáng lập lòe do sự cộng hưởng từ Zapdos. Tại mỗi ô tọa độ \((i, j)\) trong hang động có chứa một chỉ số năng lượng \(C_{i,j}\) đặc trưng. Nếu \(C_{i,j}\) là một số dương, đó là một viên đá năng lượng nguyên thủy, tỏa ra hơi ấm kỳ lạ giúp hồi phục sinh lực và tăng cường sức chiến đấu của Pikachu lên đúng bằng giá trị \(C_{i,j}\). Tuy nhiên, nếu \(C_{i,j}\) là một số âm, đó lại là một cơn ác mộng thực sự: những cái bẫy mìn tĩnh điện vô hình do bọn xấu Team Rocket bí mật giăng sẵn để săn lùng các loài Pokemon hoang dã, nếu vô tình giẫm phải, toàn bộ cơ thể Pikachu sẽ bị giật tung, làm giảm sút sức mạnh đi một lượng tương đương với trị tuyệt đối của nó \(|C_{i,j}|\).

Rất may mắn, trước khi bắt đầu chuyến đi dài ngày này, người bạn đồng hành Misty đã tinh tế dúi vào tay Ash một chiếc túi nhỏ chứa \(K\) tấm thẻ "Giải Trừ" sử dụng công nghệ lượng tử siêu việt. Mỗi khi Ash bước chân vào một ô có chứa bẫy mìn tĩnh điện (\(C_{i,j} < 0\)), cậu có quyền lựa chọn rút ra và kích hoạt một tấm thẻ Giải Trừ; luồng sóng lượng tử từ tấm thẻ sẽ ngay lập tức vô hiệu hóa mạch điện của cái bẫy tại ô đó, khiến nó trở thành một ụ đất vô hại và không làm suy giảm bất kỳ chút sức mạnh nào của Pikachu (lúc này có thể coi như \(C_{i,j} = 0\)). Dù vậy, số lượng thẻ là có hạn và chặng đường phía trước lại quá dài, cậu không thể lãng phí chúng một cách bừa bãi. Bằng nhãn quan chiến thuật nhạy bén, bạn hãy vạch ra một lộ trình di chuyển tối ưu nhất và chỉ định rõ những lúc nào cần dùng thẻ, để khi Ash và Pikachu đặt chân đến đích ở ô \((M, N)\), tổng sức mạnh mà Pikachu có thể tích lũy được trong cơ thể là con số lớn nhất có thể, chuẩn bị sẵn sàng cho cuộc đụng độ lịch sử với Zapdos.

Input

• Dòng đầu tiên chứa ba số nguyên \(M, N, K\) (\(1 \le M, N \le 500\); \(0 \le K \le 10\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên \(C_{i,j}\) (\(-10^9 \le C_{i,j} \le 10^9\)).

Output

• In ra một số nguyên duy nhất là tổng năng lượng tích lũy lớn nhất đạt được tại ô \((M, N)\).

Example

2 3 1
5 -10 2
-3 4 -1

8

3 3 0
1 2 3
4 5 6
7 8 9

29

2 2 2
-100 -100
-100 -100

-100

Scoring

• Subtask \(1\) (\(20\%\) điểm): \(1 \le M, N \le 20, K = 0\).
• Subtask \(2\) (\(30\%\) điểm): \(1 \le M, N \le 100, K \le 5\).
• Subtask \(3\) (\(50\%\) điểm): Không còn ràng buộc gì thêm.

Sau bao nỗ lực vượt qua hang động sấm sét, cơn bão bên ngoài cũng dần tan biến, để lộ ra trước mắt Ash một khung cảnh hùng vĩ đến choáng ngợp: một cánh cổng đá nguyên khối khổng lồ, cao sừng sững chạm đến những đám mây, toàn bộ bề mặt bị che phủ bởi những lớp rễ cây cổ thụ chằng chịt hàng ngàn năm tuổi. Linh cảm mách bảo cậu rằng đây chính là Ruins of Alph huyền thoại, một khu bảo tồn thiêng liêng lưu giữ những bí mật nguyên thủy nhất về sự hình thành và khởi nguyên của toàn bộ thế giới Pokemon. Khi Pikachu tò mò tiến lại gần và cọ má vào bề mặt cánh cổng để làm sạch lớp bụi rêu, hàng loạt những ký tự kỳ lạ được khắc sâu trên đá bỗng nhiên tỏa ra thứ ánh sáng xanh ngọc bích mờ ảo. Trong chớp mắt, những ký tự đó tách rời khỏi vách đá, hóa thành những sinh vật sống bay lượn vòng quanh không trung. Đó chính là những Pokemon Unown vô cùng hiếm gặp - những sinh vật không gian có hình dạng trùng khớp hoàn hảo với các chữ cái Latinh trong bảng chữ cái con người. Khi Ash vươn tay chạm nhẹ vào phần trung tâm của cánh cổng, các Unown lập tức hội tụ lại, xếp nối đuôi nhau thành một chuỗi ký tự \(S\) dài dằng dặc, chỉ bao gồm toàn các chữ cái tiếng Anh in thường, uốn lượn như một con rồng ánh sáng. Đột nhiên, một giọng nói trầm mặc, vang vọng từ cõi hư vô truyền thẳng vào tâm trí cậu, mang theo uy nghiêm của những bậc cổ nhân: "Hỡi kẻ lữ hành mang trái tim thuần khiết, để phá vỡ phong ấn và mở được cánh cổng của những người sáng thế, ngươi buộc phải thấu hiểu trọn vẹn sự 'Hài hòa' của ngôn ngữ vũ trụ này".

Nhớ lại những buổi chiều ngồi học ngoan ngoãn tại phòng nghiên cứu, Professor Oak đã từng say sưa giảng giải rằng, "Độ hài hòa" của một chuỗi văn bản cổ đại được định nghĩa một cách vô cùng khắt khe: đó chính là tổng số lượng các cặp \((A, B)\) thỏa mãn đồng thời hai điều kiện tiên quyết:

• Thứ nhất, \(A\) và \(B\) phải là hai xâu con (bao gồm các ký tự đứng liền kề nhau) hoàn toàn không giao nhau hay chồng lấn lên nhau của chuỗi gốc \(S\); nói một cách chính xác về mặt toán học, vị trí ký tự kết thúc của đoạn \(A\) bắt buộc phải nằm trước vị trí ký tự bắt đầu của đoạn \(B\) để không gây ra những nghịch lý về không thời gian.
• Thứ hai, và cũng là điều kiện khó nhằn nhất, cả đoạn văn bản \(A\) và đoạn văn bản \(B\) đều phải mang cấu trúc của một xâu đối xứng (Palindrome - nghĩa là dù ngươi có đọc từ trái sang phải hay đọc ngược từ phải sang trái thì ý nghĩa và âm điệu của chúng vẫn hoàn toàn giống hệt nhau), đại diện cho sự cân bằng âm dương tuyệt đối của vạn vật trong vũ trụ bao la.

Vì chuỗi ký tự phát sáng trên cánh cổng quá dài, bao gồm hàng vạn ký tự liên tiếp nhau, Ash hoàn toàn rơi vào trạng thái tuyệt vọng nếu phải đếm nhẩm bằng đầu óc con người. Cậu thừa hiểu rằng, nếu đưa ra một con số sai lệch dù chỉ một đơn vị, hệ thống phòng thủ quang học của di tích sẽ lập tức kích hoạt và biến cậu thành tro bụi. Thời gian không còn nhiều, hãy thể hiện tài năng lập trình xuất chúng của bạn để viết ra một chương trình thuật toán đếm chính xác số lượng cặp xâu con thỏa mãn hai điều kiện khắc nghiệt kia. Do số lượng kết quả đếm được có thể vượt qua giới hạn lưu trữ của các kiểu dữ liệu thông thường, hãy bảo vệ an toàn cho kết quả bằng cách in ra phần dư của nó khi chia cho một hằng số nguyên tố lớn là \(10^9 + 7\).

Input

• Một dòng duy nhất chứa xâu \(S\) (\(1 \le |S| \le 10^5\)) gồm các chữ cái tiếng Anh in thường (từ a đến z) tượng trưng cho chuỗi ngôn ngữ Unown phát sáng.

Output

• In ra một số nguyên duy nhất là phần dư của tổng số lượng cặp \((A, B)\) thỏa mãn điều kiện hài hòa khi chia cho \(10^9 + 7\).

Example

aba

3

aaaa

15

pokemon

21

Scoring

• Subtask \(1\) (\(30\%\) điểm): \(|S| \le 100\).
• Subtask \(2\) (\(30\%\) điểm): \(|S| \le 2000\).
• Subtask \(3\) (\(40\%\) điểm): Không còn ràng buộc gì thêm.

Sau khi đọc đúng mật mã hài hòa, cánh cổng đá ngàn năm tuổi cuối cùng cũng ầm ầm mở tung ra hai bên, thế nhưng khung cảnh chào đón Ash bên trong lại không phải là những kho báu cổ xưa hay những bí kíp huấn luyện Pokemon huyền thoại như cậu vẫn hằng mong đợi, mà thay vào đó là một căn cứ ngầm đồ sộ được xây dựng hoàn toàn bằng kim loại lạnh lẽo. Thật không thể tin nổi, tổ chức tội phạm khét tiếng Team Rocket bằng một cách mờ ám nào đó đã đi trước cậu một bước, khoan phá lòng đất và thiết lập một đại trung tâm thao túng tín hiệu vô tuyến hòng kiểm soát tâm trí của toàn bộ các loài Pokemon hoang dã sinh sống xung quanh khu vực.

Đi dọc theo hành lang trung tâm dài hun hút của căn cứ, Ash kinh ngạc phát hiện ra chúng đã rải chính xác \(N\) trạm phát sóng gây nhiễu não bộ, được xếp thành một hàng ngang thẳng tắp, sừng sững như những con quái vật sắt thép. Các thông số trên màn hình điều khiển cho thấy, trạm thứ \(i\) đang không ngừng phát ra những luồng sóng nhiễu độc hại với mức công suất kinh hoàng là \(P_i\). Nhìn những Pokemon nhỏ bé bên ngoài đang dần mất đi ý thức và trở nên hung hãn, máu nóng trong người Ash sôi lên sùng sục; cậu phẫn nộ đến tột độ trước dã tâm thâm độc này và quyết tâm phải phá hủy toàn bộ mạng lưới tín hiệu bằng chiêu đòn tấn công hệ điện tối thượng và mạnh mẽ nhất của Pikachu.

Theo lý thuyết chiến đấu, một luồng sét cực đại khi phóng ra có khả năng lan truyền qua các vật dẫn và phá hủy một dãy các trạm phát sóng đứng liên tiếp nhau. Thế nhưng, thủ lĩnh tối cao Giovanni của Team Rocket là một kẻ vô cùng gian xảo và am hiểu khoa học công nghệ. Hắn đã lường trước được những cuộc tập kích và lắp đặt lên toàn bộ hệ thống một màng lọc phản xạ điện từ thông minh: Tia sét của Pikachu chỉ có thể truyền qua và phá hủy thành công một đoạn liên tiếp các trạm nếu và chỉ nếu tập hợp công suất của các trạm nằm trong đoạn bị tấn công đó tạo thành một dãy số mà phần tử trung vị của dãy phải đạt đến hoặc vượt qua một mức ngưỡng năng lượng tới hạn \(X\) nào đó để phá vỡ rào cản.

(Để hiểu rõ hơn về hệ thống phòng thủ này, trung vị của một dãy gồm \(L\) phần tử được định nghĩa một cách chặt chẽ là phần tử đứng ở vị trí thứ \(\lfloor \frac{L+1}{2} \rfloor\) khi người ta tiến hành sắp xếp toàn bộ dãy số đó theo thứ tự tăng dần từ nhỏ đến lớn. Ví dụ, nếu đoạn tấn công trúng vào \(3\) trạm có công suất là \([4, 1, 2]\), sau khi sắp xếp lại thành \([1, 2, 4]\) thì trung vị của đoạn này chính là \(2\)).

Do Pikachu đã phải vắt kiệt sức lực sau chuỗi hành trình băng rừng vượt bão dài ngày, Ash nhẩm tính trong đầu rằng cậu chỉ có thể ra lệnh cho Pikachu gồng mình tung đòn đánh vào một đoạn liên tiếp các trạm phát sóng có độ dài chính xác bằng \(L\), không hơn không kém. Để đòn đánh tạo ra uy lực xuyên phá kinh hoàng nhất làm lõi hệ thống phòng thủ của Giovanni phải quá tải và nổ tung, Ash vô cùng khao khát muốn chọn ra một đoạn mục tiêu có độ dài \(L\) sao cho giá trị trung vị của đoạn đó đạt ngưỡng lớn nhất có thể. Giữa lằn ranh sinh tử và áp lực thời gian đang đếm ngược, bạn hãy phát huy khả năng tư duy thuật toán để tìm ra giá trị trung vị tối đa đó, giúp Ash định vị chính xác mục tiêu cần triệt hạ.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(L\) (\(1 \le L \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(P_1, P_2, \dots, P_N\) (\(1 \le P_i \le 10^9\)) mô tả công suất trạm.

Output

• In ra một số nguyên duy nhất là giá trị trung vị lớn nhất có thể đạt được của một đoạn liên tiếp các trạm có độ dài đúng bằng \(L\).

Example

5 3
1 4 2 5 3

4

6 4
10 20 30 10 20 30

20

4 2
5 10 15 20

15

Scoring

• Subtask \(1\) (\(30\%\) điểm): \(N \le 100\).
• Subtask \(2\) (\(30\%\) điểm): \(N \le 2000\).
• Subtask \(3\) (\(40\%\) điểm): Không còn ràng buộc gì thêm.

Vụ nổ kinh thiên động địa từ lõi trung tâm thao túng tín hiệu tạo ra một sức công phá quá lớn, không những làm sụp đổ hoàn toàn cơ ngơi của Team Rocket mà còn làm rung chuyển dữ dội các tầng ngậm nước sâu dưới lòng đất, dẫn đến một hệ lụy vô cùng thảm khốc: phong ấn phong thủy ở tầng sâu nhất của Ruins of Alph đã bị phá vỡ hoàn toàn! Bầu trời đỏ rực lên như máu, đất đá nứt toác, và từ trong biển lửa dung nham trào dâng, Groudon - sinh vật siêu cổ đại nắm giữ sức mạnh kiến tạo lục địa và thao túng núi lửa - đã chính thức thức tỉnh sau giấc ngủ hàng ngàn năm.

Sự phẫn nộ tột độ vì bị quấy rầy của Groudon đã lập tức chẻ đôi mặt đất, tạo ra một khe nứt dung nham khổng lồ kéo dài hàng dặm, phân chia dải bình nguyên xanh tươi phía trước mặt Ash thành \(N\) khu vực liên tiếp nhau chìm trong biển lửa. Các cảm biến nhiệt trên máy đo của hệ thống liên tục nhấp nháy ánh đèn đỏ báo động, cho biết khu vực thứ \(i\) hiện đang tỏa ra một mức nhiệt độ kinh hoàng lên tới \(T_i\) độ, đủ sức thiêu rụi mọi thứ thành tro bụi.

Tình thế lúc này thực sự ngàn cân treo sợi tóc: nếu không tìm cách làm nguội dòng chảy của khe nứt này trong vòng vài phút tới, hàng ngàn tấn dung nham sẽ tràn ra ngoài, hủy diệt sinh thái của toàn bộ phần còn lại của Viridian Forest và đe dọa sinh mạng của hàng vạn sinh linh. Không chần chừ nửa giây, Ash lập tức tung quả Pokeball chứa Lapras ra ngoài, khẩn thiết yêu cầu người bạn hệ Nước/Băng của mình sử dụng chiêu thức "Tia Băng Giá Tuyệt Đối" (Sheer Cold) để dập tắt ngọn lửa địa ngục.

Tuy nhiên, việc đóng băng cả một đại dương dung nham không phải là chuyện đơn giản. Để kiểm soát luồng năng lượng khổng lồ không bị phản hệ, cậu bắt buộc phải chia \(N\) khu vực dung nham này thành đúng \(K\) đoạn liên tiếp nhau để Lapras lần lượt đóng băng từng đoạn một. Theo cơ chế vật lý phép thuật của chiêu thức này, nếu Lapras nhắm mục tiêu đóng băng một đoạn bao gồm các khu vực trải dài từ vị trí \(L\) đến vị trí \(R\), lượng sinh lực và năng lượng phép thuật mà Lapras bị rút cạn cho đoạn đó sẽ bằng bình phương của tổng nhiệt độ của tất cả các khu vực nằm trong đoạn đó: \((\sum_{i=L}^R T_i)^2\).

Suy ra, tổng năng lượng tiêu tốn của Lapras cho toàn bộ chiến dịch giải cứu này chính là tổng năng lượng làm nguội cộng dồn của cả \(K\) đoạn. Ash cần phải thiết lập một chiến thuật phân chia các khu vực thành đúng \(K\) đoạn sao cho tổng năng lượng tiêu tốn của Lapras được ép xuống mức nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) (\(1 \le K \le N \le 10^5\); \(1 \le K \le 20\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(T_1, T_2, \dots, T_N\) (\(1 \le T_i \le 10^4\)).

Output

• In ra một số nguyên duy nhất đại diện cho mức năng lượng tiêu tốn tối thiểu của Lapras.

Example

4 2
1 2 3 4

52

5 3
4 5 1 2 3

77

3 1
10 10 10

900

Scoring

• Subtask \(1\) (\(20\%\) điểm): \(N \le 100\), \(K \le 10\).
• Subtask \(2\) (\(30\%\) điểm): \(N \le 2000\), \(K \le 20\).
• Subtask \(3\) (\(50\%\) điểm): Không còn ràng buộc gì thêm.

Khoảnh khắc Lapras đóng băng thành công tấc dung nham cuối cùng của Groudon, Ash chưa kịp thở phào nhẹ nhõm thì cảnh vật không gian xung quanh bỗng chốc méo mó, rạn nứt như những mảnh thủy tinh vỡ vụn. Lực hấp dẫn hoàn toàn đảo lộn, vạn vật mất trọng lượng, và cậu nhận ra mình đã bị hút sâu vào một thực tại hoàn toàn khác: Chiều Không Gian Ảo Ảnh - tàn dư vĩ đại và cũng là cạm bẫy cuối cùng, đáng sợ nhất của Team Rocket. Kẻ đứng sau giật dây mọi chuyện, thao túng vạn vật nãy giờ từ từ hạ cánh xuống từ bầu trời hắc ám. Không ai khác, đó chính là thực thể đột biến Mewtwo, nhưng giờ đây nó đang ở trong một trạng thái tồi tệ tột độ: toàn bộ cơ thể bị kìm kẹp bởi một bộ giáp hắc ám công nghệ cao do Giovanni chế tạo nhằm kiểm soát trí não của nó. Ánh mắt Mewtwo đỏ ngầu sự thịnh nộ và mất kiểm soát. Để ngăn cản bước tiến của Ash, Mewtwo sử dụng siêu năng lực khuếch đại vô cực của mình, ngay lập tức phân rã các hạt ánh sáng và tạo ra \(N\) ảo ảnh phân thân bay lơ lửng, thoắt ẩn thoắt hiện khắp mọi ngóc ngách của không gian đa chiều này. Theo phân tích thần tốc từ hệ thống siêu máy tính vệ tinh của Professor Oak truyền xuống Pokedex, mỗi một ảo ảnh không chỉ là một cái bóng vô tri, mà chúng mang theo một đoạn mã gen di truyền nhân tạo được biểu diễn dưới dạng một số nguyên không âm cực kỳ phức tạp. Dãy mã gen của \(N\) phân thân này được hệ thống đánh số thứ tự từ \(1\) đến \(N\) lần lượt mang các giá trị là \(A_1, A_2, \dots, A_N\).

Nhiệm vụ cứu rỗi thế giới đặt trọn lên vai Ash: để phá vỡ kết giới hắc ám dày đặc này và giải cứu linh hồn Mewtwo khỏi sự kiểm soát bạo chúa của bộ giáp, Ash phải ra lệnh cho 3 Pokemon chủ lực của mình đứng thành đội hình tam giác, đồng loạt tụ khí để tung ra đòn tấn công hợp thể huyền thoại mang tên "Tri-Attack". Điều kiện tiên quyết là cậu cần phải khóa máy nhắm chuẩn xác vào đúng 3 phân thân mục tiêu trên bầu trời (do tính chất lượng tử của ảo ảnh, cậu hoàn toàn có thể chọn lặp lại cùng một vị trí phân thân nhiều lần cho các tia đánh khác nhau, tức là phải chọn ra một bộ ba chỉ số ngắm bắn \((i, j, k)\) với điều kiện \(1 \le i, j, k \le N\)). Sự kết hợp năng lượng tinh khiết của 3 phân thân bị đánh trúng sẽ sinh ra một vụ nổ cộng hưởng hạ nguyên tử, làm triệt tiêu hoàn toàn và vĩnh viễn năng lượng hắc ám của không gian chiều sâu này nếu và chỉ nếu mã gen của ba phân thân đó giao thoa và triệt tiêu lẫn nhau về mức 0 tuyệt đối. Ngôn ngữ của máy tính diễn giải điều này như sau:

(Trong đó, AND là phép toán thao tác bit chuẩn - Bitwise AND, so sánh từng bit nhị phân một của ba con số). Trận chiến sinh tử này chỉ còn được tính bằng từng tích tắc nhỏ nhoi, vạn vật sắp sụp đổ. Bạn hãy dốc toàn bộ vốn liếng của một cao thủ lập trình thi đấu để giúp Ash tính toán khẩn cấp xem tổng cộng hệ thống radar có bao nhiêu bộ ba chỉ số ngắm bắn \((i, j, k)\) thỏa mãn điều kiện triệt tiêu tuyệt đối này.

Lưu ý quan trọng: Cấu trúc tọa độ ngắm \((1, 2, 3)\) và \((2, 1, 3)\) được coi là hai phương án khóa mục tiêu hoàn toàn khác nhau biệt lập, bởi vì thứ tự phân công mục tiêu cho 3 Pokemon của Ash là khác nhau.

Input

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 10^6\)).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(0 \le A_i < 2^{20}\)).

Output

• In ra một số nguyên duy nhất là tổng số lượng bộ ba chỉ số \((i, j, k)\) hợp lệ để kích hoạt thành công Đòn Đánh Ba Tia.

Example

3
1 2 4

24

4
3 5 6 7

6

5
0 0 0 0 0

125

Scoring

• Subtask \(1\) (\(20\%\) điểm): \(N \le 100\), \(A_i < 2^{10}\).
• Subtask \(2\) (\(30\%\) điểm): \(N \le 5000\), \(A_i < 2^{12}\).
• Subtask \(3\) (\(50\%\) điểm): Không còn ràng buộc gì thêm.