Cho một dãy ~p_1,p_2,...,p_n~ là một hoán vị của ~1,2,...,n~. Bạn được thực hiện hai phép biến đổi sau:

• Chọn hai phần tử bất kì và tráo đổi,loại phép biến đổi này chỉ được thực hiện nhiều nhất một lần.
• Chọn hai phần tử kề nhau và tráo đổi, loại phép biến đổi này được thực hiện nhiều lần.

Yêu cầu: Tính số phép biến đổi ít nhất để đưa dãy hoán vị ~p_1,p_2,...,p_n~ về dãy hoán vị ~1,2,3...,n~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~p_1,p_2,...,p_n~.

Output

• In ra số bước ít nhất để đưa dãy ~p~ về hoán vị ~1,2,3,...,n~.

Constraints .

• ~1 \le N \le 10^5~.

Subtask

• Sub ~1~ ~(10\%)~: ~n = 3~.
• Sub ~2~ ~(20\%)~: ~n \le 30~.
• Sub ~3~ ~(20\%)~: ~n \le 300~.
• Sub ~4~ ~(20\%)~: ~n \le 1000~.
• Sub ~5~ ~(15\%)~: ~n \le 10^4~.
• Sub ~6~ ~(15\%)~: ~n \le 10^5~.

Sample Input 1

5
5 3 4 2 1

Sample Output 1

3

Interpool (tên gọi tắt của International Pool Championship) là giải đấu bộ môn bi-a có quy mô lớn nhất thế giới với tổng giá trị giải thưởng lên đến 1,000,000 BTC.

Giải đấu được tổ chức với thể thức như sau:

• Có ~2\times n~ cơ thủ được chia thành ~n~ cặp đấu.
• Một cơ thủ khi tham gia thi đấu trong một trận đấu thì chỉ có thể thắng hoặc thua.
• Ban đầu cả ~2\times n~ cơ thủ đều ở nhánh thắng.
• Các cơ thủ ở nhánh thắng sẽ bắt cặp thi đấu với nhau. Các cơ thủ thắng sẽ tiếp tục ở nhánh thắng, trong khi đó các cơ thủ thua sẽ xuống nhánh thua.
• Các cơ thủ ở nhánh thua sẽ bắt cặp thi đấu với nhau. Các cơ thủ thắng sẽ tiếp tục ở nhánh thua, trong khi đó các cơ thủ thua sẽ bị loại khỏi giải đấu.
• Quy trình này sẽ diễn ra liên tục cho đến khi chỉ còn một cơ thủ ở nhánh thắng và một cơ thủ ở nhánh thua. Hai cơ thủ này sẽ bắt cặp với nhau và thi đấu một trận chung kết để tìm ra nhà vô địch.

Ví dụ: Với giải đấu có ~8~ cơ thủ, các trận đấu sẽ được tổ chức như sau:

Ta thấy, giải này sẽ có tổng cộng ~14~ trận đấu.

Cho số nguyên dương ~k~. Biết rằng có ~2^k~ cơ thủ tham gia giải đấu này. Hãy tính tổng số trận đấu diễn ra.

Input

Gồm một dòng chứa số nguyên dương ~k~ ~(1\le k\le 10^{18})~.

Output

Số lượng trận đấu diễn ra. Vì kết quả có thể rất lớn nên hãy in ra phần dư của kết quả sau khi chia cho ~10^9+7~.

Ví dụ

Input

3

Output

14

Scoring

• Subtask ~1 \ (30\%)~: ~k \le 60~;
• Subtask ~2 \ (70\%)~: Không có ràng buộc gì thêm.

Nobita sắp phải làm bài kiểm tra và nhiệm vụ của cậu ấy là học thuộc một xâu ~S~ gồm ~n~ ký tự. Tuy nhiên, vì học dốt nên Nobita không thể nhớ được xâu này và cần đến sự trợ giúp của bánh mì trí nhớ của Doraemon.

Trớ trêu thay là ở vũ trụ này, để bánh mì trí nhớ hoạt động thì cậu ấy phải giải được một câu đố. Nhiệm vụ của Nobita là phải đếm số xâu con liên tiếp của xâu ~S~ sao cho tồn tại một hoán vị của xâu con đó là một xâu đối xứng. Một xâu được gọi là đối xứng khi xâu đó đọc từ trái sang phải và từ phải sang trái đều giống nhau.

Hãy giúp Nobita giải câu đố trên để mở khoá sức mạnh của bánh mì trí nhớ.

Input

• Dòng đầu tiên chứa số nguyên dương ~n \ (1\le n\le 10^5)~;
• Dòng thứ hai chứa xâu ~S~ gồm ~n~ ký tự là các chữ cái trong bảng chữ cái tiếng Anh.

Output

Một số nguyên là số xâu con thoả mãn.

Ví dụ

Input

5
aabcc

Output

10

Scoring

• Subtask ~1 \ (30\%)~: ~n \le 200~;
• Subtask ~2 \ (40\%)~: ~n \le 1000~;
• Subtask ~3 \ (30\%)~: Không có ràng buộc gì thêm.

Là thương hiệu vang bóng một thời, hình ảnh bao diêm Thống Nhất có in hình chú chim bồ câu trắng tung bay trên nền trời xanh đã trở thành một ký ức khó quên của nhiều thế hệ người Việt. Vào những năm nửa cuối của thế kỷ trước, khi hầu hết gia đình Việt vẫn sử dụng bếp than và bếp củi để sinh hoạt, những bao diêm có hình chim bồ câu trắng trên nền trời xanh là hình ảnh quen thuộc và trở thành sản phẩm không thể thiếu trong đời sống, sinh hoạt của người Việt Nam.

Ba que diêm có thể xếp thành hình tam giác nếu có thể xếp được chúng trên mặt bàn sao cho mỗi cạnh của tam giác được tạo thành bởi một que diêm và các que diêm giao nhau tại đầu mút của nó. Ví dụ, ba que diêm có độ dài ~(3, 4, 5)~ có thể tạo thành hình tam giác, trong khi đó ba que diêm có độ dài ~(1, 2, 4)~ thì không.

Tèo là chàng trai thích lập trình nên Tèo muốn cho Bờm chơi một trò chơi. Trò chơi hoạt động như sau: Tèo có ~n~ que diêm được đánh số thứ tự từ ~1~ đến ~n~ theo chiều từ trái sang phải. Que diêm thứ ~i~ có độ dài ~a_i~ ~(1\le i\le n)~. Tèo yêu cầu Bờm thực hiện một trong hai việc sau:

• 1 p x: Thay que diêm ở vị trí ~p~ bằng một que diêm khác có độ dài ~x~;
• 2 l r: Đếm xem trong các que diêm có vị trí từ ~l~ đến ~r~, có bao nhiêu bộ ba các que diêm khác nhau có thể xếp thành hình tam giác.

Nếu Bờm trả lời đúng tất cả các yêu cầu loại ~2~, Tèo sẽ thưởng Bờm một chiếc máy đào coin có cấu hình khoẻ hơn cả máy tính lượng tử. Nhưng Bờm mới học Toán nên không thể giải quyết được bài toán này nên cần đến sự trợ giúp của bạn. Hãy giúp cho Bờm chiến thắng trò chơi này nhé!

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, q~ ~(1 \le n, q\le 10^5)~ là số que diêm và số câu hỏi của Tèo;
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1\le a_i\le 10, 1\le i\le n)~ mô tả độ dài của từng que diêm;
• Mỗi dòng trong số ~q~ dòng tiếp theo mô tả một yêu cầu của Tèo, bắt đầu bằng một số nguyên mô tả loại yêu cầu ~(1~ hoặc ~2)~, tiếp theo:
  • Với yêu cầu loại ~1~: hai số nguyên dương ~p, x~ ~(1\le p\le n; \ 1\le x\le 10)~ mô tả vị trí đổi diêm và độ dài que diêm thay thế;
  • Với yêu cầu loại ~2~: hai số nguyên dương ~l, r~ ~(1\le l, r\le n, \ r - l \ge 2)~.

Output

Với mỗi yêu cầu loại ~2~, in ra một số nguyên trên một dòng là đáp án của truy vấn đó.

Ví dụ

Input

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

Output

1
1
4
0

Giải thích

Với yêu cầu đầu tiên, ta có các bộ ba que diêm sau:

• ~(a_1, a_2, a_3)~ với độ dài lần lượt là ~1, 3, 4~;
• ~(a_1, a_2, a_4)~ với độ dài lần lượt là ~1, 3, 5~;
• ~(a_1, a_3, a_4)~ với độ dài lần lượt là ~1, 4, 5~;
• ~(a_2, a_3, a_4)~ với độ dài lần lượt là ~3, 4, 5~.

Trong đó chỉ có bộ ba que diêm ~(a_2, a_3, a_4)~ có thể xếp thành tam giác.

Sau yêu cầu thứ hai, độ dài của các que diêm trở thành ~[\textbf{2}, 3, 4, 5, 4, 4, 1]~.

Với yêu cầu thứ ba, bộ ba que diêm duy nhất ~(a_1, a_2, a_3)~ với độ dài lần lượt là ~2, 3, 4~ có thể xếp thành tam giác.

Với yêu cầu thứ tư, ta có các bộ ba que diêm sau:

• ~(a_3, a_4, a_5)~ với độ dài lần lượt là ~4, 5, 4~;
• ~(a_3, a_4, a_6)~ với độ dài lần lượt là ~4, 5, 4~;
• ~(a_3, a_5, a_6)~ với độ dài lần lượt là ~4, 4, 4~;
• ~(a_4, a_5, a_6)~ với độ dài lần lượt là ~5, 4, 4~.

Cả bốn bộ ba que diêm trên đều có thể xếp thành tam giác.

Sau yêu cầu thứ năm, độ dài của các que diêm trở thành ~[2, 3, 4, \textbf{10}, 4, 4, 1]~.

Với yêu cầu thứ sáu, bộ ba que diêm duy nhất ~(a_3, a_4, a_5)~ với độ dài lần lượt là ~4, 10, 4~ không thể xếp thành tam giác.

Scoring

• Subtask ~1 \ (25\%)~: ~n \le 100; \ q\le 20~;
• Subtask ~2 \ (25\%)~: ~q\le 20~;
• Subtask ~3 \ (25\%)~: Chỉ có yêu cầu loại ~2~;
• Subtask ~4 \ (25\%)~: Không có ràng buộc gì thêm.