Vào dịp lễ tình nhân, anh chàng đào hoa Phú Lâm đã gửi ~n~ bức thư chúc mừng đến ~n~ người yêu của mình (giả sử tên của họ đều khác nhau). Tuy nhiên, đáng tiếc là Phú đã mắc nhầm lẫn không hề nhẹ nên đã gửi sai địa chỉ hết các bức thư, vì thế cô ~X~ thì nhận thư của cô ~Y~, cô ~Y~ thì nhận thư của cô ~Z~, ... Thế là sau đợt lễ đáng nhớ đó, cả ~n~ cô gái đã cùng chia tay Phú Lâm. Câu hỏi đặt ra là Phú có bao nhiêu cách thực hiện lỗi sai đó, tức là gửi thư cho các cô gái mà không ai nhận đúng lá thư của họ?

Input

Số nguyên dương ~n~ duy nhất với ~1 \le n \le 10^6.~

Output

Kết quả của bài toán, lấy modulo ~10^9+7.~

Sample input 1

4

Sample output 1

9

Sample input 2

12345

Sample output 2

137669039

Một hôm Quýt đã làm ra những món ăn tuyệt vời để mời Chưng ăn trưa. Nhưng nào lại có chuyện dễ như vậy. Vẫn như mọi khi Quýt bắt Chưng giải một câu đố sau thì mới được ăn cơm. Với một số n cho trước Chưng hãy tìm hai số ~a~ và ~b~ sao cho:

~\bullet \space a> 0, \space a \le b~

~\bullet \space a+b = n~

~\bullet \space gcd(a, b)~ là lớn nhất có thể.

Bạn hãy giúp Chưng mau mau tìm hai số này để có thể thưởng thức bữa trưa nhé.

Input

• Một dòng duy nhất gồm một số ~n (2 \le n \le 10^{12})~.

Output

• Một dòng duy nhất gồm hai số nguyên ~a~ và ~b~ thỏa mãn nếu có nhiều cặp ~a,b~ thoả mãn hay đưa ra cặp giá trị với ~a~ là nhỏ nhất.

Sample Input 1

75

Sample Output 1

25 50

Một hôm Chưng và Quýt đi lạc vào một lưới ô vuông kích thước n×m. Ô ~(1, 1)~ ở góc dưới trái, ô ~(n,m)~– trên phải. Có ~k~ ô chứa chướng ngại vật, ô thứ ~i~ ở tọa độ ~(xi, yi), 1 ≤ xi ≤ n, 1 ≤ yi ≤ m.~ Không có chướng ngại vật ở ô ~(1, 1)~ và ~(n, m)~. Hiện tại Chưng đang ở ô ~(1, 1)~, và Quýt đang ở ô ~(n, m)~. Vì đây là một vùng đất đặc biệt nên ở mỗi bước Chưng chỉ được chuyển sang ô kề cạnh bên phải hoặc bên trên nếu ô tới không chứa chướng ngại vật. Hãy xác định số lượng đường đi mà Chưng có thể tìm thấy Quýt khi đi từ ô ~(1, 1)~ đến ô ~(n, m)~ và đáp án phải mô đun cho ~10^9+7~.

Input

• Dòng đầu tiên chứa 3 số nguyên ~n, m, k~ ~(1 ≤ n, m ≤ 10^5, 0 ≤ k ≤ 100)~. Nếu ~k > 0~, dòng thứ ~i~ trong ~k~ dòng tiếp theo chứa 2 số nguyên ~xi, yi (1 ≤ xi ≤ n, 1 ≤ yi ≤ m)~.

Output

• Một số nguyên không âm – số lượng đường tìm được theo mô đun ~10^9+7~.

Sample Input 1

5 6 3 
2 2
3 5
4 2

Sample Output 1

25

Một hôm Chưng và Quýt được giao nhiệm vụ dọn dẹp tấm bảng sau nhà. Tấm bản là một bàn cờ kích thước nxm ô, các hàng được đánh số từ trên xuống dưới từ 1 đến n, các cột đánh số từ 1 đến m từ trái qua phải. Giao giữa hàng ~a~ và cột ~b~ là ô ~(a, b)~. Mỗi ô của bàn cờ được sơn một trong 2 màu trắng hoặc đen, nếu ~a+b~ là số chẵn – ô có màu trắng, trong trường hợp ngược lại – màu đen. Tai hoạ là gần đây Chưng đã học thêm được cho mình một kỹ năng vẽ ux, ui design mới nên bỗng nhiên cậu nổi máu nghệ sĩ, muốn dùng các hộp sơn phun cạnh đó tạo một bức tranh trừu tượng bằng cách sơn đảo màu một số ô, tức là ô trắng thành ô đen và ngược lại.

Quýt là một người vốn say mê tin học và thiết kế nên không thể khoanh tay đứng nhìn bạn vẽ như vậy. Quýt nghĩ thầm, thà sơn sao cho tồn tại một t để các ô ở các dòng từ t trở lên có màu đen, các ô còn lại (từ dòng t+1 trở xuống) – có màu trắng. Ít ra như vậy cũng còn dùng như tấm bảng vừa có thể viết phấn (ở phần màu đen) và viết bút dạ (ở phần màu trắng). Lứu ý trong trường hợp bảng toàn màu đen vẫn chấp nhận.

Cứ mỗi lần sơn lại một ô, Chưng lại đứng ngắm nhìn và suy nghĩ chọn ô tiếp theo, còn Quýt thì nhẩm tính bây giờ phải sơn đổi màu ít nhất bao nhiêu ô để tạo thành bảng 2 phần như mình muốn. Vốn có trí nhớ tốt, Quýt nhớ hết các số đó. Sau khi Chưng sơn lại ô thứ q thì sự kiên nhẫn của Quýt cũng cạn kiệt, cô dứt khoát yêu cầu Chưng khiêng bảng đi cất. Khi ra về, những số đã nhớ trong dãy tính được vẫn hiện rõ trong đầu của Quýt Vì vậy bạn hãy cùng Chưng thử đoán xem những số đó là những số nào?

Input

• Dòng đầu tiên chứa 2 số nguyên ~n~ và ~m~ ~(1 ≤ n ≤ 2×10^5, 1 ≤ m ≤ 10)~,

• Dòng thứ hai chứa số nguyên ~q~ ~(1 ≤ q ≤ 2×10^5)~,

• Mỗi dòng trong q dòng tiếp theo chứa 2 số nguyên ~a~ và ~b~ ~(1 ≤ a ≤ n, 1 ≤ b ≤ m).~

Output

• Các số đã nhẩm tính được theo trình tự tính, mỗi số trên một dòng.

Sample Input 1

5 4
4
1 1
5 1
1 3
2 3

Sample Output 1

9
8
7
8

Trong một khu rừng ảo diệu, Quýt là một nhà thám hiểm đầy tò mò và thông minh. Một ngày, Quýt tình cờ phát hiện ra một khu rừng kỳ lạ, nơi có một cây thần kỳ với N đỉnh lung linh sắc màu được đánh số từ ~1~ đến ~N~, và ~N-1~ cạnh uốn lượn giữa chúng như những dấu nối của vận mệnh. Chiều cao của cây không phải là đo lường bằng mét hay feet, mà bằng số lượng cạnh trên hành trình xa xôi nhất từ rễ đâm sâu dưới đất đến đỉnh cao nhất nơi cành lá sum suê. Mỗi ngày, Quýt lại đắm mình trong việc tìm hiểu về cây thần kỳ này, nghiên cứu từng con đường, từng nhánh lá, và từng gốc rễ của nó. Một hôm, Chưng, bạn của Quýt, đến thăm. Chưng là một học giả trẻ tuổi, nhưng cũng không kém phần sáng suốt và ham học hỏi. Quýt đưa ra một câu hỏi thách thức trí tuệ của bạn mình: Cậu có biết nếu mỗi nút được coi là một nút gốc, thì chiều cao của cây khi đó là bao nhiêu không?. Hãy giúp Chưng.

Input

• Dòng đầu tiên gồm số nguyên ~N~ ~(2\le N \le 100000)~. ~N-1~ dòng tiếp theo mỗi dòng gồm hai số nguyên ~a~ và ~b~ ~(1 \le a,b \le N)~ mô tả cạnh vô hướng nối giữa ~a~ và ~b~

Output

• Đưa ra ~N~ dòng, dòng thứ ~i~ là chiều cao của cây nếu coi nút thứ ~i~ là nút gốc

Sample Input 1

11
2 1
3 1
4 1
5 2
6 2
7 3
10 7
11 7
8 4
9 4

Sample Output 1

3
4
3
4
5
5
4
5
5
5
5

Từ ngày vào học ở IUH, Lộc và Tài là đôi bạn thân thiết, làm gì cũng chung. Ăn chung bàn, ở chung phòng (KTX), ngủ chung giường (tầng), thi chung team và lên lãnh thưởng chung (nhì chuyên Tin). Hai bạn cũng là niềm tự hào của các thầy Luna và Tina. Tuy nhiên, thực ra hai bạn cũng so kè nhau rất nhiều, đến mức từ bạn thân mà có những giai đoạn không nhìn mặt nhau, trở thành người xa lạ. Trong suốt quãng đời sinh viên, hai bạn đã học cùng lúc nhiều môn và đạt được tổng cộng ~n~ cột điểm. Trộm vía là hai bạn chưa có điểm nào bị zero, và điểm là số nguyên dao động từ ~1~ đến ~10.~ Câu hỏi đặt ra là ai có tổng điểm lớn hơn và ai có tích các điểm chia hết cho tích các điểm của người còn lại? Bạn thử giúp hai bạn trả lời câu hỏi vui này nhé, hiện tại hai bạn đang làm người xa lạ rồi.

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~1 \le n \le 10^5.~

Trong hai dòng tiếp theo là dãy ~n~ điểm của Lộc và Tài.

Output

In ra "Loc", "Tai", "Hoa" lần lượt ứng với tổng Lộc lớn, tổng Tài lớn hơn, tổng bằng nhau. Tương tự, in ra "Loc", "Tai", "Hoa" lần lượt ứng với tích Lộc chia hết cho tích Tài (và lớn hơn tích Tài), tích Tài chia hết cho tích Lộc (và lớn hơn tích Lộc), không tích nào chia hết cho tích nào (hoặc hai tích bằng nhau).

Sample input 1

3 
10 10 10
10 10 10

Sample output 1

Hoa Hoa

Sample input 2

2
1 10
4 5

Sample output 2

Loc Tai

Dennis Vũ là một cậu bé đặc biệt, có đam mê lập trình từ nhỏ. Khi lên ba tuổi, thay vì học bảng cửu chương thì Vũ đã học xử lý bit. Vào một ngày nọ, bố cho Vũ một cặp số ~a, b, c~ nguyên dương và hỏi ~a+b+c~ bằng mấy? Thay vì tính ra giá trị đó, Vũ đã trả lời bố các kết quả

~a\; OR \; b \; OR \; c \text{ và } a \; XOR \; b \; XOR \; c \text{ và } a \; AND \; b \; AND \; c~

làm bố rất sửng sốt. Hỏi Vũ tính có đúng không, và nếu tính đúng thì giá trị ~a+b+c~ bằng mấy?

Input

Ba giá trị ~a\; OR \; b \; OR \; c \text{ và } a \; XOR \; b \; XOR \; c \text{ và } a \; AND \; b \; AND \; c~ mà Vũ tính được, trong đó ~0 \le a, b, c \le 2^{31}.~

Output

Nếu Vũ tính sai, tức là không có bộ số ~a,b,c~ nào thỏa mãn thì in ra ~-1~, ngược lại thì in ra ~a+b+c.~

Sample input 1

15 3 2

Sample output 1

31

Sample input 2

1 100 100

Sample output 2

-1

Robert Duong Hoan là một đại kiện tướng cờ vua của CLB H3.2 với thành tích bất bại trong những lần tham gia hội thao toàn trường. Tuyệt kỹ của anh là: phế hậu tạo sát cục, chiếu hết trong vòng 10 nước, phong tỏa quân bắt tượng, chiếu rút bắt xe, ... đã là nỗi ám ảnh của các cao thủ. Với sự tin tưởng của người hâm mộ, anh đã được giao tổ chức một giải đấu rất đặc sắc nhân dịp kỷ niệm ngày 26/3. Luật chơi như sau:

• Nếu hiện có ~n~ chẵn kỳ thủ thì họ sẽ chia cặp và thi đấu loại trực tiếp, ai thua sẽ bị loại ngay; giải đấu sẽ tiếp tục với ~n/2~ kỳ thủ còn lại.
• Nếu hiện có ~n~ lẻ kỳ thủ thì họ sẽ thi đấu vòng tròn tính điểm (mỗi người đấu với tất cả những người kia), đấu tổng cộng ~n(n-1)/2~ ván (chú ý nếu ~n=1~ thì không cần đấu nữa); xong là kết thúc luôn.

Giả sử rằng không có trận nào hòa. Chẳng hạn: nếu có ~28~ kỳ thủ thì: lượt 1 họ đấu cặp với tổng ~14~ ván, còn ~14~ kỳ thủ; lượt 2 họ lại đấu cặp, thêm ~7~ ván và còn ~7~ kỳ thủ; lượt 3 do còn lẻ kỳ thủ nên họ đấu vòng tròn, thêm ~7(7-1)/2=21~ ván và kết thúc. Tổng cộng có ~14+7+21=42~ ván.

Robert được giao tổ chức đúng ~m~ ván đấu, nhưng bạn ấy thắc mắc rằng số kỳ thủ ít nhất cần mời để có số trận đấu như thế là bao nhiêu. Bạn hãy giúp bạn ấy với nhé.

Input

Một số nguyên dương ~m~ duy nhất là số ván đấu, với ~1 \le m \le 10^{18}.~

Output

Số kỳ thủ ít nhất cần mời. Nếu không tồn tại cách mời thi in ra ~-1.~

Sample input 1

42

Sample output 1

28

Sample input 2

1

Sample output 2

2