Nhật Huy có ~n~ cái kẹo và muốn chia hết số kẹo này cho ba bạn Mayly, Peace và Sunny. Biết rằng:

• Mayly không muốn số lượng kẹo mình được nhận là một số chia hết cho ~2~.
• Peace không muốn số lượng kẹo mình được nhận là một số chia hết cho ~3~.
• Sunny không muốn số lượng kẹo mình được nhận là một số chia hết cho ~4~.
• Tất cả các bạn đều không muốn số lượng kẹo mình được nhận bằng với số lượng kẹo mà người khác được nhận.

Huy muốn nhờ bạn tính xem Huy có bao nhiêu cách chia kẹo thỏa mãn. Các bạn hãy tính giúp Huy nhé.

Dữ liệu - Nhập từ tệp văn bản CANDY.inp:

• Một dòng duy nhất gồm một số nguyên dương ~n~ - số kẹo mà Huy có ~(1 \le n \le 10^6)~.

Kết quả - Ghi ra tệp văn bản CANDY.out:

• Một dòng duy nhất gồm số cách chia kẹo thỏa mãn.

Chấm điểm

Ví dụ

Dữ liệu (CANDY.inp)

6

Kết quả (CANDY.out)

3

Giải thích

Có ~3~ cách chia thỏa mãn như sau:

• Cách 1: Mayly nhận được ~1~ cái kẹo, Peace nhận được ~2~ cái kẹo, Sunny nhận được ~3~ cái kẹo.
• Cách 2: Mayly nhận được ~3~ cái kẹo, Peace nhận được ~1~ cái kẹo, Sunny nhận được ~2~ cái kẹo.
• Cách 3: Mayly nhận được ~3~ cái kẹo, Peace nhận được ~2~ cái kẹo, Sunny nhận được ~1~ cái kẹo.

Huy có một dãy số gồm ~2n~ phần tử ~a_1, a_2, ..., a_{2n}~, trong đó mỗi số nguyên dương không lớn hơn ~n~ xuất hiện đúng hai lần. Huy định nghĩa khoảng cách của một vị trí ~i~ trong dãy số và một cặp phần tử cùng có giá trị ~j~ là ~D(i, j)~, được tính theo công thức:

$$D(i, j) = (|x_j - i| + 1) \times (|y_j - i| + 1)$$

trong đó ~x_j, y_j~ là hai vị trí của hai phần tử có giá trị ~j~.

Huy muốn tính xem với mỗi vị trí ~i~ thì khoảng cách gần nhất giữa ~i~ và một cặp phần tử bất kỳ là bao nhiêu, hay nói cách khác Huy muốn tìm giá trị ~D(i, j)~ nhỏ nhất với mọi ~j~. Tuy nhiên do số vị trí quá lớn nên Huy không thể tính nhanh được, các bạn hãy giúp Huy nhé.

Dữ liệu - Nhập từ tệp văn bản PAIR.inp:

• Dòng đầu tiên gồm một số nguyên dương ~n~ ~(1 \le n \le 10^5)~.
• Dòng tiếp theo gồm ~2n~ số nguyên dương ~a_1, a_2, ..., a_{2n}~ ~(1 \le a_i \le n)~.
• Dữ liệu đầu vào đảm bảo trong dãy ~a~ có đúng hai phần tử có giá trị ~i~ với mỗi ~i~ thỏa mãn ~1 \le i \le n~.

Kết quả - Ghi ra tệp văn bản PAIR.out:

• Một dòng duy nhất gồm ~2n~ số nguyên dương, số nguyên dương thứ ~i~ là khoảng cách ngắn nhất của một cặp số bất kỳ với vị trí ~i~.

Chấm điểm

Ví dụ

Dữ liệu (PAIR.inp)

2
1 2 2 1

Kết quả (PAIR.out)

4 2 2 4

Giải thích

• Cặp phần tử có giá trị ~1~ xuất hiện tại hai vị trí ~1~ và ~4~.
• Khoảng cách giữa vị trí ~1~ và cặp phần tử có giá trị ~1~ là: $$D(1, 1) = (|x_1 - 1| + 1) \times (|y_1 - 1| + 1) = (|1 - 1| + 1) \times (|4 - 1| + 1) = 4$$
• Cặp phần tử gần nhất với vị trí ~1~ và vị trí ~4~ là cặp phần tử có giá trị ~1~, với khoảng cách là ~4~.
• Cặp phần tử gần nhất với vị trí ~2~ và vị trí ~3~ là cặp phần tử có giá trị ~2~, với khoảng cách là ~2~.

Huy có một dãy số ~a_1, a_2, ..., a_n~. Huy có thể thực hiện ~k~ lần biến đổi, mỗi lần Huy có thể thay đổi một chữ số trong dãy. Huy muốn tổng các số chia hết cho ~9~ trong dãy là lớn nhất có thể. Bạn hãy tìm cách để Huy có thể biến đổi dãy số thỏa mãn yêu cầu. Lưu ý rằng sau khi biến đổi có thể có một hoặc nhiều số bắt đầu bằng chữ số ~0~.

Dữ liệu - Nhập từ tệp văn bản DIV.inp:

• Dòng đầu tiên gồm hai số nguyên dương ~n, k~ ~(1 \le n \le 2000, 0 \le k \le 10000)~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^9)~.

Kết quả - Ghi ra tệp văn bản DIV.out:

• Một dòng duy nhất gồm tổng các số chia hết cho ~9~ trong dãy sau khi biến đổi.

Chấm điểm

Ví dụ

Dữ liệu (DIV.inp)

4 2
28 4 20 7

Kết quả (DIV.out)

117

Giải thích

Huy có thể thay đổi chữ số cuối cùng của phần tử đầu tiên thành chữ số ~7~, sau đó thay đổi chữ số đầu tiên của phần từ thứ ba thành chữ số ~9~ để được tổng ~27 + 90 = 117~. Có thể thấy đây là tổng lớn nhất có thể tạo được.

Cho ba giá trị nguyên không âm ~n, s~ và ~m~.

Một viên ngọc có thể cấu tạo bởi ~n~ loại nguyên tố khác nhau. Với 1mg nguyên tố thứ ~i~ xuất hiện trong viên ngọc sẽ làm tăng giá trị viên ngọc thêm ~2^{i - 1}~ đơn vị.

Cấu tạo của hai viên ngọc là khác nhau nếu tồn tại một loại nguyên tố mà hàm lượng của của nguyên tố này trong viên ngọc ở hai cấu tạo là khác nhau.

Nhiệm vụ của bạn là đếm số lượng cấu tạo khác nhau của các viên ngọc có giá trị ~x~ sao cho ~0 \leq x \leq 2^n - 1~ và ~x \mod m = s~.

Giải thích về cấu tạo một viên ngọc: Giả sử viên ngọc có giá trị là ~x = 6~, các cấu tạo khác nhau có thể của viên ngọc là:

• 6mg nguyên tố thứ nhất: ~x = 6\times 2^0 = 6\times 1 = 6~.
• 4mg nguyên tố thứ nhất, 1mg nguyên tố thứ hai: ~x = 4\times 2^0 + 1\times 2^1 = 4\times 1 + 1\times 2 = 6~.
• 2mg nguyên tố thứ nhất, 2mg nguyên tố thứ hai: ~x = 2\times 2^0 + 2\times 2^1 = 2\times 1 + 2\times 2 = 6~.
• 2mg nguyên tố thứ nhất, 1mg nguyên tố thứ ba: ~x = 2\times 2^0 + 1\times 2^2 = 2\times 1 + 1\times 4 = 6~.
• 3mg nguyên tố thứ hai: ~x = 3\times 2^1 = 3\times 2 = 6~.
• 1mg nguyên tố thứ hai, 1mg nguyên tố thứ ba: ~x = 1\times 2^1 + 1\times 2^2 = 1\times 2 + 1\times 4 = 6~.

Dữ liệu - Nhập từ tệp văn bản PEARL.inp:

• Một dòng duy nhất chứa ba số nguyên ~n, s~ và ~m~ ~(1 \leq n \leq 100, 0 \leq s < m \leq 1000)~.

Kết quả - Ghi ra tệp văn bản PEARL.out:

• Một dòng duy nhất chứa kết quả bài toán. Do kết quả có thể rất lớn, hãy in ra dưới dạng modulo ~10^9 + 7~.

Chấm điểm

Ví dụ

Dữ liệu (PEARL.inp)

3 1 5

Kết quả (PEARL.out)

7

Giải thích

• Các giá trị ~x~ thoả mãn ~0 \leq x \leq 2^n - 1~ và ~x \mod m = s~ là ~1~ và ~6~. Với ~x = 1~ có ~1~ cấu tạo khác nhau, với ~x = 6~ có ~6~ cấu tạo khác nhau.

Dữ liệu (PEARL.inp)

7 0 100

Kết quả (PEARL.out)

9829

Giải thích

• Các giá trị ~x~ thoả mãn ~0 \leq x \leq 2^n - 1~ và ~x \mod m = s~ là ~0~ và ~100~. Với ~x = 0~ có ~1~ cấu tạo khác nhau, với ~x = 100~ có ~9828~ cấu tạo khác nhau.

Dữ liệu (PEARL.inp)

36 0 100

Kết quả (PEARL.out)

275724118

Hôm nay, Dung muốn cho Huy một thử thách nho nhỏ về Toán học.

Dung có một dải băng dài được chia thành ~n~ ô vuông được đánh số thứ tự từ ~1~ đến ~n~ từ trái sang phải. Ban đầu, mỗi ô vuông trên băng đều ghi số ~1~. Huy có thể yêu cầu Dung thực hiện các thao tác sau:

• ~+\ i\ j\ k~: Cộng hai số ở vị trí ~i~ và ~j~, sau đó ghi kết quả vào ô ở vị trí ~k~.
• ~*\ i\ j\ k~: Nhân hai số ở vị trí ~i~ và ~j~, sau đó ghi kết quả vào ô ở vị trí ~k~.

Lưu ý, ~i, j, k~ có thể giống nhau.

Dung sẽ cho Huy một số nguyên dương ~n~. Gọi ~p_i~ là số nguyên tố thứ ~i~. Cô có 4 loại thử thách như sau:

• Loại 1: Với mọi ô từ ~1~ đến ~n~, Huy cần biến đổi sao cho ô ~i~ ghi giá trị ~i~.
• Loại 2: Với mọi ô từ ~1~ đến ~n~, Huy cần biến đổi sao cho ô ~i~ ghi giá trị ~p_i~.
• Loại 3: Với mọi ô từ ~1~ đến ~n~, Huy cần biến đổi sao cho ô ~i~ ghi tổng các giá trị ~j^3~ với ~j~ là ước của ~i~. Ví dụ, ô ~4~ sẽ ghi giá trị ~1^3 + 2^3 + 4^3 = 73~.
• Loại 4: Với mọi ô từ ~2~ đến ~n~, Huy cần biến đổi sao cho ô ~i~ ghi lập phương tổng các giá trị ~p_j~ với ~j~ là ước nguyên tố của ~i~. Ví dụ, ô ~6~ sẽ ghi giá trị ~(p_2 + p_3)^3 = (3 + 5)^3 = 512~. Ô ~1~ cần ghi giá trị ~1~.

Để hoàn thành thử thách, Huy được phép yêu cầu Dung thực hiện thao tác biến đổi không quá ~50000~ lần.

Các bạn hãy viết chương trình giúp Huy hoàn thành thử thách nhé.

Dữ liệu - Nhập từ tệp văn bản ARRAY.inp:

• Một dòng duy nhất gồm hai số nguyên dương ~n, \theta~, với ~\theta~ là loại thử thách của Dung. ~(1 \le n \le 20000, 1 \le \theta \le 4)~

Kết quả - Ghi ra tệp văn bản ARRAY.out:

• Dòng đầu tiên gồm một số nguyên dương ~k~ là số lần Dung cần thực hiện thao tác biến đổi. ~(0 \le k \le 50000)~
• ~k~ dòng tiếp theo, mỗi dòng thuộc một trong hai dạng sau:
  • ~+\ i\ j\ k~: mô tả thao tác cộng. ~(1 \le i, j, k \le n)~
  • ~*\ i\ j\ k~: mô tả thao tác nhân. ~(1 \le i, j, k \le n)~

Chấm điểm

Ví dụ

Dữ liệu (ARRAY.inp)

2 2

Kết quả (ARRAY.out)

2
+ 1 1 1
+ 1 2 2

Giải thích

• Đầu tiên, Huy lấy giá trị của ô đầu tiên cộng với chính nó và ghi vào ô đầu tiên. Kết quả là ~1 + 1 = 2~.
• Tiếp theo, Huy lấy giá trị của ô đầu tiên cộng với giá trị của ô thứ hai và ghi vào ô thứ hai. Kết quả là ~2 + 1 = 3~.