Cho số nguyên dương n, bạn được phép sử dụng không giới hạn các số tự nhiên từ 1 tới n. Hỏi có bao nhiêu cách chọn ra 1 dãy có tổng các phần tử bằng n.

Đầu vào: Dòng duy nhất chứa số nguyên dương n

Ràng buộc: 1 <= n <= 10^12

Đầu ra: In ra đáp án của bài toán sau khi chia dư với 10^9 + 7

Input:

6

Output:

32

Cho hai dãy số A (N phần tử) và B (M phần tử). Hãy tìm độ dài của dãy con chung của A và B sao cho dãy con đó là dãy tăng dần.

Dữ liệu vào:

Dòng 1: Số nguyên N (1 <= N <= 500).

Dòng 2: N số nguyên A[i].

Dòng 3: Số nguyên M (1 <= M <= 500).

Dòng 4: M số nguyên B[i].

Dữ liệu ra:

Độ dài LCIS.

Ví dụ:

Input:

5 
1 4 2 3 5 
4 
4 2 3 5

Output:

3

Bạn được cho một mảng gồm n số nguyên, và nhiệm vụ của bạn là tìm bốn giá trị (tại bốn vị trí khác nhau) sao cho tổng của chúng bằng x.

Input:

Dòng đầu tiên chứa hai số nguyên n và x — kích thước mảng và tổng cần tìm.

Dòng thứ hai chứa n số nguyên a₁, a₂, …, aₙ — các giá trị trong mảng.

Output:

In ra bốn số nguyên: chỉ số của bốn phần tử tạo thành tổng x.

Nếu có nhiều đáp án, bạn có thể in ra bất kỳ một đáp án nào.

Nếu không có lời giải, in ra IMPOSSIBLE.

Ràng buộc:

~1 \le n \le 1000~

~1 \le x,a_i \le 10^9~

Ví dụ :

Input:

8 15
3 2 5 8 1 3 2 3

Output:

1 2 4 7

Cho mảng A gồm N số nguyên và một số K. Em được phép chọn một phần tử bất kỳ và lật ngược dấu của nó (nhân với -1). Thao tác này PHẢI được thực hiện đúng K lần (một phần tử có thể bị lật nhiều lần). Hãy tìm tổng lớn nhất của các phần tử trong mảng sau khi lật đủ K lần.

Dữ liệu vào:

Dòng 1: Hai số nguyên N và K (1 <= N <= 10^5; 1 <= K <= 10^4).

Dòng 2: N số nguyên Ai (-100 <= Ai <= 100).

Kết quả ra: Tổng lớn nhất đạt được.

Ví dụ:

Input:

4 1
4 2 3 -1

Output:

10

(Chỉ lật số -1 thành 1. Mảng trở thành 4, 2, 3, 1 -> Tổng 10).