Lộc đang được đào tạo để trở thành một chuyên gia đánh máy hàng đầu cho dự án IUH Coder. Leader của em ấy đã giao một nhiệm vụ về nhà là đánh máy một xâu ký tự in hoa "F", "O" và "X". Lộc đang ăn kem que vào một chiều đông nóng bức và vẫn hy vọng hoàn thành nhiệm vụ này thật nhanh. Em ấy muốn cầm que kem bằng một tay và gõ bằng tay kia. Thật không may, Lộc vẫn còn là một cậu bé mới lớn và mỗi bàn tay của cậu quá nhỏ để có thể chạm hết bàn phím. Em chỉ có thể chạm tới các chữ cái "F" và "X" bằng tay trái và các chữ cái "F" và "O" bằng tay phải.

Xét một xâu ~W~ mà Lộc phải gõ. Lộc có thể bắt đầu gõ bằng bất kỳ tay nào (tay kia cầm que kem). Sau đó, có thể em phải đổi tay nếu cần để gõ các chữ cái theo đúng thứ tự. Gọi ~F(W)~ là số lần tối thiểu Lộc phải đổi tay để gõ một xâu ~W~ như vậy (trong suốt quá trình đó, một tay em luôn cầm que kem và gõ bằng tay còn lại). Ví dụ: nếu ~W = XXFFOOF~ thì Lộc cần phải đổi tay ít nhất ~1~ lần: gõ ~X,X,F,F~ bằng tay trái, rồi đổi tay để gõ ~O,O,F~ bằng tay phải; còn nếu ~W = OOOOO~ thì Lộc không cần đổi tay lần nào cả.

Yêu cầu đặt ra là cho một xâu ~S~ có độ dài ~N~, gọi ~G(S)~ là tổng của ~F(W)~ trên tất cả các xâu con ~W~ của ~S~ (xâu con là một tập con các ký tự liên tiếp của xâu ban đầu). Lưu ý rằng có tất cả ~1+2+...+N = \frac{N(N+1)}{2}~ xâu con như vậy. Hãy giúp Lộc tính giá trị của ~G(S)~ modulo ~10^9+7.~

Input: dòng đầu tiên gồm số ~N~ là độ dài của xâu với ~1 \le N \le 8.10^5~, dòng tiếp theo là xâu cần gõ.

Output: kết quả của bài toán.

Sample input 1:

3

XFO

Sample output 1:

1

Sample input 2:

10

FXXFXFOOXF

Sample output 2:

36

Giải thích:

Ta thấy rằng chuỗi ~XFO~ có các chuỗi con là: ~X, F, O, XF, FO, XFO~ trong đó chỉ có chuỗi cuối mới cần đổi tay để gõ, còn lại hoàn toàn có thể gõ bằng 1 tay.

Ngay từ những ngày đầu được học Toán, về số học Nam rất thích tìm hiểu các số nguyên tố, còn về hình học thì bạn chỉ thích tìm hiểu hình chữ nhật. Hôm nay, tham gia thi Olympic Tin học, Nam lại may mắn được gặp một bài toán liên quan đến số nguyên tố và hình chữ nhật như sau: Cho một bảng lưới hình chữ nhật gồm ~m~ dòng và ~n~ cột. Các dòng được đánh số từ ~1~ đến ~m~ từ trên xuống dưới; các cột được đánh số từ ~1~ đến ~n~ từ trái sang phải. Ô giao giữa dòng ~i~ với cột ~j~ gọi là ô ~(i,j)~ có ghi một số nguyên dương ~A_{ij}.~

Yêu cầu đặt ra là đếm số lượng hình chữ nhật con của bảng lưới trên (hình chữ nhật có các cạnh song song hoặc trùng với các cạnh của bảng lưới) thỏa mãn điều kiện trong ~4~ ô nằm trên ~4~ góc của hình chữ nhật con có ít nhất ~3~ ô có giá trị là số nguyên tố (độ dài mỗi cạnh phải lớn hơn 1). Tất nhiên không phải thích cái nào cũng giỏi về cái đó, Nam vẫn đang loay hoay giải quyết vấn đề này, hãy giúp bạn ấy nhé.

Input: Dòng 1 chứa 2 số nguyên dương ~m,n~ với ~1 < m,n \le 300~. Dòng thứ ~i~ trong ~m~ dòng sau mỗi dòng chứa ~n~ số nguyên dương được điền trong dòng tương ứng, các số không vượt quá ~10^6.~

Output: Một số nguyên duy nhất là số lượng hình chữ nhật tìm được.

Sample input:

3 4

1 2 3 4

1 2 3 4

1 2 3 5

Sample output:

7

* Ràng buộc:*

• Có ~30\%~ số test tương ứng với ~m,n \le 10.~
• Có ~40\%~ số test tương ứng với ~10 <m,n \le 60.~</li>
• Có ~30\%~ số test tương ứng với ~60 <m,n \le 300.~</li>

Là một đại gia khét tiếng trong vùng, để nâng cao năng suất sản xuất chuẩn bị cho dịp Tết, Phú ông vừa đầu tư mua một dây chuyền các cánh tay tự động đóng gói các hộp bánh. Trên một băng chuyền, Phú ông có ~n~ hộp bánh cần được đóng gói xếp thành một hàng từ trái sang phải. Hộp thứ ~i~ có khối lượng là ~{{w}_{i}}~ với ~1\le i\le n~. Do đặc thù của dây chuyền sản xuất, hệ thống chỉ có thể sử dụng hai cánh tay robot đóng gói hộp bánh nằm ở hai đầu băng chuyền như sau:

• Cánh tay bên trái đóng gói được hộp ở đầu phía bên trái băng chuyền và tốn một năng lượng là ~l~ nhân với khối lượng của hộp đó.
• Cánh tay bên phải đóng gói được hộp ở đầu phía bên phải băng chuyền và tốn một năng lượng là ~r~ nhân với khối lượng của hộp đó.

Các hộp sau khi đóng gói sẽ được mang ra ngoài, không tính trong hàng đó nữa. Nếu chỉ còn lại 1 hộp trên hàng thì nó có thể sử dụng cánh tay trái hay phải đều được.

Tuy nhiên, do hệ thống có một chút trục trặc nhỏ nên khi cánh tay ở cùng một bên được sử dụng hai lần liên tiếp thì nó đòi hỏi thêm một ít năng lượng nữa, cụ thể ~L~ cho bên trái và ~R~ cho bên phải. Hãy giúp Phú ông xác định năng lượng nhỏ nhất mà robot cần sử dụng để đóng gói hết các hộp bánh.

Input. Dòng đầu tiên là 5 số theo thứ tự là ~n,l,r,L,R~ với ~1\le n\le {{10}^{5}},\text{ }1\le l,r\le 100,\text{ }1\le L,R\le {{10}^{4}}~.

Dòng tiếp theo là ~n~ số nguyên dương ~{{w}_{1}},{{w}_{2}},...,{{w}_{n}}~ với ~1\le {{w}_{i}}\le 100,\text{ }i=1,2,3,...,n.~

Output. Một số nguyên dương duy nhất chỉ năng lượng ít nhất mà hệ thống cần sử dụng.

Sample input 1.

3 4 4 18 1

42 3 90

Sample output 1.

540

Sample input 2.

4 7 2 3 9

1 2 3 4

Sample output 2.

34

Giải thích. Trong VD thứ nhất, do ~l=r~ nên có thể dùng cánh tay bên trái hay bên phải đều không ảnh hưởng; do đó, để tránh các năng lượng tiêu tốn ~L,R~, có thể cho cánh tay trái và phải thay phiên đóng gói các hộp bánh và năng lượng cần dùng là ~4\cdot (42+3+90)=540~. Trong VD thứ hai, cách tốt nhất là dùng cánh tay phải trước, rồi đến cánh tay trái, cuối cùng, sử dụng cánh tay phải hai lần thì năng lượng cần dùng là ~2\cdot 4+7\cdot 1+2\cdot (3+2)+9=34~.

Trung đang học Nhập môn lập trình về phần mảng 1 chiều và được thầy Tình giao cho một bài toán "đơn giản" như sau: cho một mảng số nguyên dương có ~n~ phần tử ~a_1, a_2, ..., a_n~ và các phần tử có giá trị không vượt quá ~n~. Đếm xem có bao nhiêu cặp chỉ số ~(L,R)~ với ~1 \le L < R \le n~ sao cho ~a_L \neq a_R~ và với mọi ~i~ mà ~L < i < R~ thì ~a_i~ cũng phải khác ~a_L, a_R.~

Với số ~n~ nhỏ, Trung có thể giải bài toán trong vòng một nốt nhạc. Tuy nhiên, thầy đã tăng độ khó lên bằng cách cho ~n~ rất lớn và thuật toán của Trung đòi hỏi chương trình chạy quá lâu. Hãy giúp Trung tìm cách tối ưu nhé.

Input: dòng đầu tiên gồm số nguyên dương ~n~ với ~2 \le n \le 2.10^5.~ Dòng tiếp theo gồm các phần tử là các số nguyên dương của mảng (các số không nhất thiết phân biệt).

Output: đáp số của bài toán.

Sample input:

4

3 1 4 2

Sample output:

6

Giải thích các cặp chỉ số ~(L,R)~ có thể là ~(1,2),(2,3),(3,4),(1,4),(1,3),(2,4)~. Vì tất cả các số hạng của dãy đều đôi một phân biệt nên cứ chọn bất kỳ cặp chỉ số nào cũng đều thỏa mãn.

Bạn Nhân rất thích làm việc với các con số và bạn ấy đang nghiên cứu một cách biểu diễn các số trong những hệ cơ số khác nhau. Với mỗi số nguyên dương ~n~ trong hệ thập phân có dạng ~n=\overline{{{a}_{k}}{{a}_{k-1}}...{{a}_{2}}{{a}_{1}}{{a}_{0}}},~ trong đó ~0\le {{a}_{i}}\le 9,i=\overline{0,k}~, Nhân viết nó thành

~n={{a}_{k}}{{10}^{k}}+{{a}_{k-1}}{{10}^{k-1}}+...+{{a}_{2}}{{10}^{2}}+{{a}_{1}}{{10}^{1}}+{{a}_{0}}{{10}^{0}}.~

Và Nhân đã nghĩ ra một hệ cơ số khá đặc biệt và bạn rất thích thú với nó, đặt tên là hệ ~10'~ phân. Một số viết trong hệ ~10'~ – phân dạng ~n={{\overline{{{a}_{k}}{{a}_{k-1}}...{{a}_{2}}{{a}_{1}}{{a}_{0}}}}_{(1{0}')}}~ với ~0\le {{a}_{i}}\le 9,i=0..k~ sẽ có giá trị trong hệ thập phân thông thường là

~n={{a}_{k}}({{10}^{k}}+1)+{{a}_{k-1}}({{10}^{k-1}}+1)+...+{{a}_{2}}({{10}^{2}}+1)+{{a}_{1}}({{10}^{1}}+1)+{{a}_{0}}({{10}^{0}}+1)~.

Bằng hệ cơ số này, Nhân có thể mã hóa một số nguyên dương ~K~ nào đó bằng cách nhân giá trị của nó trong hệ thập phân và trong hệ ~10'~ – phân lại để được một số nguyên dương ~N~. Nhân đang thắc mắc là với số nguyên dương ~N~ cho trước thì số nguyên dương ~K~ nhỏ nhất là bao nhiêu. Bạn hãy giúp Nhân thực hiện công việc này nhé, sắp tốt nghiệp tới nơi rồi, không còn thời gian để vét cạn nữa.

Yêu cầu. Cho số nguyên dương ~N~ thỏa mãn ~0<N<{{10}^{18}}~. Hãy tìm số nguyên dương ~K~ nhỏ nhất sao cho giá trị của nó trong hệ thập phân và trong hệ ~10'~ – phân có tích bằng ~N~.</p>

Input. Một dòng duy nhất là số nguyên dương ~N~.

Output. Một dòng duy nhất là số nguyên dương ~K.~ Nếu không có số ~K~ nào thỏa mãn thì in ra ~-1.~

Sample input 1.

2

Sample output 1.

1

Sample input 2.

110

Sample output 2.

10

Năm nay kỳ thi Olympic SV được tổ chức tại trường Sư phạm kỹ thuật nhưng nhà trường đã triển khai tham quan làng Đại học bên cạnh với nhiều địa điểm kỳ thú. Làng này này có ~n~ địa điểm (đánh số từ 1 đến ~n~) và được nối với nhau bằng ~m~ con đường hai chiều để có thể đi từ bất kỳ địa điểm nào đến bất kỳ địa điểm nào khác. Trong số ~n~ địa điểm này, có ~k~ địa điểm hấp dẫn các Sinh viên đến tham qan du lịch. Khánh An là một thí sinh tham dự kỳ thi và lần đầu tiên được đến làng, nên An muốn thăm tất cả k địa điểm hấp dẫn trên.

Ban đầu An đang ở địa điểm ~1~. Khi đi từ địa điểm này đến địa điểm khác sẽ mất một số thời gian di chuyển. Trong đó có điều đặc biệt là An có thể di chuyển tức thời từ địa điểm hấp dẫn đang tham quan hiện tại đến một địa điểm hấp dẫn đã tham quan mà không mất thời gian di chuyển nào (việc di chuyển tức thời không mất thời gian di chuyển này cho phép An di chuyển nhanh chóng giữa các địa điểm của làng).

Bạn hãy giúp An tính tổng thời gian di chuyển tối thiểu để tham quan tất cả k địa điểm hấp dẫn. Chú ý rằng ta chỉ quan tâm đến thời gian di chuyển, chứ không quan tâm đến thời gian tham quan tại địa điểm đó và không nhất thiết phải quay trở về địa điểm 1 khi kết thúc hành trình.

Ví dụ mạng lưới địa điểm và đường đi như hình vẽ sau. Các địa điểm biểu thị bởi các đường tròn và các địa điểm hấp dẫn 2,4,5 được biểu thị bởi các đường tròn tô kín. Các đoạn thẳng nối hai đường tròn biểu thị một con đường nối hai địa điểm tương ứng. Các số viết trên mỗi đoạn thẳng biểu thị thời gian di chuyển giữa hai địa điểm.

Một hành trình của An thăm tất cả các địa điểm hấp dẫn với tổng thời gian di chuyển tối thiểu là:

• Bắt đầu từ địa điểm 1 đến địa điểm 2 (địa điểm hấp dẫn): thời gian di chuyển là 2;
• Tiếp theo đến địa điểm 3: thời gian di chuyển là 1;
• Tiếp theo đến địa điểm 5 (địa điểm hấp dẫn): thời gian di chuyển là 2;
• Tiếp theo, do địa điểm 5 hiện tại là hấp dẫn nên di chuyển tức thời (không mất thời gian) trở lại địa điểm hấp dẫn 2: thời gian di chuyển là 0;
• Sau đó đến địa điểm 4 (địa điểm hấp dẫn), rồi kết thúc hành trình: thời gian di chuyển là 3.

Tổng thời gian di chuyển của hành trình trên là: ~2+1+2+0+3=8~.

Input: Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ trong đó ~1 \le n \le 10^5, \, 0 \le m \le 10^5~ cho biết có bao nhiêu địa điểm và con đường trong thành phố. Dòng thứ ~i~ trong ~m~ dòng tiếp theo chứa ba số nguyên ~u_i,v_i,w_i~ với ~1 \le u_i, v_i \le n~ và ~1 \le w_i \le 10^9~ mô tả của một con đường hai chiều nối hai địa điểm ~u_i,v_i~ và thời gian cần thiết để đi từ địa điểm này đến địa điểm kia bằng con đường này là ~w_i.~ Hai địa điểm bất kỳ được nối với nhau không quá một con đường. Dữ liệu đảm bảo rằng có thể đi từ bất kỳ địa điểm nào đến bất kỳ địa điểm nào khác. Dòng tiếp theo chứa số nguyên ~k~ là số địa điểm hấp dẫn. Dòng tiếp theo chứa ~k~ số nguyên phân biệt ~p_1,p_2,…,p_k~ cho biết số thứ tự của các địa điểm hấp dẫn.

Output: Số nguyên duy nhất là thời gian di chuyển tối thiểu để An tham quan tất cả các địa điểm hấp dẫn. Chú ý rằng thứ tự tham quan các địa điểm hấp dẫn là tùy ý.

Sample input:

5 6

1 2 2

2 3 1

2 4 3

3 4 5

3 5 2

4 5 4

3

4 5 2

Sample output:

8

• Có ~10\%~ số test ứng với ~k=1;~
• Có ~10\%~ số test khác ứng với ~k=n;~
• Có ~20\%~ số test khác ứng với ~1 \le n \le 10;\, 0 \le m \le 10; 1 \le w_i \le 10^2; 1<k<n;~</li>
• Có ~20\%~ số test khác ứng với ~1 \le n \le 10^2;\, 0 \le m \le 10^2; 1 \le w_i \le 10^5;1<k<n;~</li>
• Có ~20\%~ số test khác ứng với ~1 \le n \le 10^3; \, 0 \le m \le 10^3;1<k<n;~</li>
• Có ~20\%~ số test còn lại không có ràng buộc gì thêm.

Trung là một lập trình viên điện toán đám mây. Hiện tại, anh ấy đang cần phải chạy tổng cộng ~n~ chương trình mô phỏng trên "đám mây". Mỗi chương trình chạy mất đúng 1 đơn vị thời gian, nhưng bộ nhớ chúng sử dụng có thể khác nhau. Bộ nhớ cần thiết cho chương trình ~i~ là ~a_i~ megabyte. Theo công việc, Trung phải chia ~n~ chương trình thành ~k~ tác vụ và số chương trình trong mỗi tác vụ không nhất thiết bằng nhau. Trong mỗi tác vụ, các chương trình được chạy lần lượt, tức là thời gian thực hiện một tác vụ sẽ bằng số chương trình trong tác vụ đó. Mặt khác, bộ nhớ được cấp phát cho mỗi tác vụ bằng bộ nhớ tối đa cần thiết cho bất kỳ một chương trình nào trong tác vụ đó.

Tuy nhiên, Trung phải trả chi phí cho mỗi megabyte trên một đơn vị thời gian, vì vậy chi phí cho mỗi tác vụ bằng số đơn vị thời gian thực hiện tác vụ đó nhân với bộ nhớ tối đa của các chương trình trong tác vụ và bằng số chương trình của tác vụ đó nhân với bộ nhớ tối đa của các chương trình trong tác vụ. Chi phí thực hiện ~n~ chương trình sẽ là tổng chi phí thực hiện ~k~ tác vụ. Bạn hãy giúp Trung chia tác vụ phù hợp sao cho chi phí thực hiện chúng là tối thiểu nhé.

Input: Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ (~1 \le k \le n \le 10^5~). Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,...,a_n~ với ~0 \le a_i \le 10^{12}~.

Output: một số nguyên là chi phí tối thiểu mà Trung phải trả.

Sample input:

10 4

4 1 12 17 7 3 6 8 10 16

Sample output:

94

Trong ví dụ trên, Trung cần chia thành 4 tác vụ như sau:

• Tác vụ 1: Gồm các chương trình thứ nhất, thứ hai và thứ sáu. Chi phí của tác vụ 1 là: ~3 \times \max(a_1,a_2,a_6 )=12;~
• Tác vụ 2: Gồm các chương trình thứ ba và thứ chín. Chi phí của tác vụ 2 là: ~2 \times \max(a_3,a_9 )=24;~
• Tác vụ 3: Gồm các chương trình thứ năm, thứ bảy và thứ tám. Chi phí của tác vụ 3 là: ~3 \times \max(a_5,a_7,a_8 )=24;~
• Tác vụ 4: Gồm các chương trình thứ tư và thứ mười. Chi phí của tác vụ 4 là: ~2 \times \max(a_4,a_{10} )=34.~

Tổng chi phí Trung cần phải trả là: ~12+24+24+34=94.~