Cho số nguyên dương \(𝑛\). Hỏi có bao nhiêu cặp số nguyên dương (\(𝑎;𝑏\)) thỏa mãn:

• \(𝑎+𝑏=𝑛\)
• \(𝑎>𝑏\)

Input

• Đọc từ file văn bản DEMCAP.INP một dòng duy nhất chứa số nguyên dương \(𝒏\ (𝟏≤𝒏≤𝟐 \times 𝟏𝟎^𝟗)\).

Output

• Ghi ra file văn bản DEMCAP.OUT một số nguyên duy nhất là số lượng cặp thỏa mãn của testcase.

Example

9

4

Viết chương tìm phần dư của tích các số từ \(𝑙\) đến \(𝑟\) chia cho \(2022\)

Input

• Đọc từ file văn bản MULM.INP một dòng duy nhất chứa hai số nguyên \(𝒍,𝒓\ (𝟏≤𝒍≤𝒓≤𝟏𝟎^{𝟏𝟖})\).

Output

• Ghi ra file văn bản MULM.OUT một số nguyên duy nhất là phần dư của tích các số \(𝑙×(𝑙+1)×(𝑙+2)×…×𝑟\) chia cho \(2022\).

Scoring

• Subtask 1 (80%): \(𝑟−𝑙≤10^6\).
• Subtask 2 (20%): \(1≤𝑙,𝑟≤10^{18}\)

Example

2019 2021

2016

Example

2016 2019

360

Mừng năm mới Nhâm Dần 2022, cửa hàng \(𝑋\) có chương trình ưu đãi khách hàng như sau: Giảm \(𝑇\) đồng, trong đó \(𝑇\) là ước chung lớn nhất của giá trị các mặt hàng có trong đơn hàng. Chương trình chỉ áp dụng cho đơn hàng có ít nhất hai mặt hàng khác nhau. Nếu đơn hàng có 3 mặt hàng khác nhau có giá trị các mặt hàng lần lượt là 6,6,10 thì sẽ được giảm 2 đồng. Lưu ý mặt hàng khác nhau nhưng giá tiền vẫn có thể bằng nhau. Nguyên là một người yêu thích các chương trình giảm giá, tuy nhiên Nguyên không biết chọn mua những mặt hàng nào sao cho số tiền được giảm là nhiều nhất. Bạn hãy giúp Nguyên nhé! Yêu cầu: Cho giá trị của 𝑛 mặt hàng, hãy giúp Nguyên chọn một số mặt hàng sao cho số tiền được giảm là nhiều nhất.

Input

Đọc từ file văn bản DISCOUNT.INP có cấu trúc:

• Dòng đầu chứa số nguyên dương \(n\ (1<n≤2\times 10^5)\), số lượng mặt hàng của cửa hàng \(X\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,…,a_n(a_i≤10^7)\), với \(a_i\) là giá tiền của mặt hàng thứ \(i\).

Output

• Ghi ra file văn bản DISCOUNT.OUT duy nhất một số nguyên là giá tiền giảm giá nhiều nhất..

Scoring

• 50% test: \(𝑛≤10^3\) và \(𝑎_𝑖≤10^7\).
• 30% test: \(10^3<𝑛≤10^5\) và \(𝑎_𝑖≤10^4\).
• 20% test: \(10^3<𝑛≤2 \times 10^5\) và \(𝑎_𝑖≤10^7\).

Example

5
3 14 15 7 9

7

Một xâu được gọi là đối xứng khi viết từ phải qua trái hay từ trái qua phải thì xâu đó không thay đổi. Nguyên là một người rất yêu thích xâu đôi xứng và các bài toán liên quan về nó. Vào một ngày, anh ấy gặp bài toán như sau: Cho trước một xâu \(𝑆\) gồm ký tự in hoa 𝐴−𝑍. Hãy đếm số lượng xâu đối xứng có thể thu được bằng cách sắp xếp lại các ký tự trong xâu \(𝑆\).

Tuy rất giỏi về các bài toán về xâu đối xứng, nhưng hiện tại anh ấy vẫn chưa thể nghĩ ra ý tưởng cho bài toán này. Vì thế anh ấy rất muốn bạn giải quyết bài toán này.

Input

• Đọc từ file văn bản CNTPALIN.INP có một dòng duy nhất chứa xâu \(s\).

Output

• Ghi ra file văn bản CNTPALIN.OUT một số nguyên là số lượng xâu đối xứng có thể thu được (lấy phần dư của kết quả khi chia cho \(𝑀=10^9+7\)).

Scoring

• 50% test: Độ dài của xâu \(𝑆\) không quá 10 ký tự.
• 50% test: Độ dài của xâu \(𝑆\) không quá \(10^6\) ký tự.

Example

ABBAA

2