Ôn luyện vào chuyên Tin #07

Một số tự nhiên được gọi là số yêu thương nếu nó là một số đối xứng, và có số lượng chữ số là số chẵn.

Yêu cầu: Cho số tự nhiên \(n(n \leq 10 ^ {100000})\). Hãy tìm số yêu thương thứ \(n\).

Input

• Số nguyên dương \(n(n \leq 10 ^ {100000})\).

Output

• Số yêu thương thứ \(n\).

Chú ý: Nếu có nhiều kết quả thì chỉ ghi ra số lớn nhất trong các kết quả tìm được.

Example

1 

11

10 

1001

Cho 1 số nguyên dương \(n\) là tích của \(m\) số nguyên tố (\(m\) số nguyên tố này không nhất thiết phải khác nhau). Ta có \(n=p_1 \times p_2 \times ... \times p_m\).

Yêu cầu: Hãy tìm tích các ước của n.

Input

• Dòng đầu tiên chứa số nguyên dương \(m\) \((m \leq 200000)\).
• Dòng tiếp theo gồm \(m\) số nguyên tố \((2 \leq p_i \leq 200000, ∀ i:1 \leq i \leq m)\).

Output

• Phần dư của tích các ước của số \(n\) khi chia cho \(10^9+7\).

Example

2
2 3 

36

3
2 3 2 

1728

Cho trước một số nguyên dương \(n\). Một số nguyên dương vừa có phần dư là 1 khi bị chia bởi \(n\) ,vừa là số chính phương thì được gọi là số bích phương.

Yêu cầu: Cho số nguyên dương \(n\) (\(n \leq 10 ^ 9\)). Hãy tìm số bích phương lớn nhất nhỏ hơn \(n^2\).

Input

• Số nguyên dương \(n\) (\(2 \leq n \leq 10 ^ 9\)).

Output

• Số bích phương lớn nhất nhỏ hơn \(n ^ 2\).

Example

2 

1

4 

9