Một robot bắt đầu ở vị trí 0 trên trục tọa độ ~Ox~. Robot thực hiện các bước di chuyển như sau:

• Bước 1: sang phải ~a~ đơn vị
• Bước 2: sang trái ~b~ đơn vị
• Bước 3: sang phải ~a~ đơn vị
• Bước 4: sang trái ~b~ đơn vị
• ... và tiếp tục xen kẽ như vậy.

Hãy xác định vị trí cuối cùng của robot sau ~k~ bước.

Input

Một dòng chứa ba số nguyên ~a, b, k~ — đơn vị dịch chuyển và số bước (~1 \le a, b, k \le 10^9~).

Output

Một dòng duy nhất là vị trí cuối cùng của robot trên trục ~Ox~ sau ~k~ bước.

Sample Input 1

5 2 3

Sample Output 1

8

Cho dãy số ~a_1, a_2, ..., a_n~ là các số nguyên dương. Cho thêm số nguyên dương ~m~. Nhiệm vụ của bạn là đếm số lượng cặp chỉ số ~(i, j)~ thỏa mãn:

• ~1 \le i < j \le n~
• ~a_i \pmod m = a_j \pmod m~

Input

• Dòng đầu chứa hai số nguyên ~n, m~ (~1 \le n, m \le 10^6~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^9~).

Output

Một dòng duy nhất là số lượng cặp ~(i, j)~ thỏa mãn điều kiện.

Sample Input 1

3 2
2 3 4

Sample Output 1

1

Giải thích: Các phần dư theo mod 2 là: 0, 1, 0 -> cặp (1, 3) cùng dư 0.

Subtasks

Một số nguyên dương ~n~ được gọi là số Kaprekar nếu thỏa mãn điều kiện sau:

• Bình phương ~n~ thu được một số có tối đa ~2d~ chữ số, trong đó ~d~ là số chữ số của ~n~.
• Chia số bình phương thành hai phần: phần bên phải có đúng ~d~ chữ số, phần bên trái là phần còn lại (có thể rỗng).
• Cộng hai phần này lại, nếu kết quả bằng chính ~n~ thì ~n~ là số Kaprekar.

Ví dụ:

• ~9^2 = 81~, chia thành 8 và 1, tổng ~8 + 1 = 9 \to 9~ là số Kaprekar.
• ~45^2 = 2025~, chia thành 20 và 25, tổng ~20 + 25 = 45 \to 45~ là số Kaprekar.

Yêu cầu: cho hai số nguyên ~L, R (L \le R)~, liệt kê tất cả các số Kaprekar trong đoạn ~[L, R]~.

Input

Một dòng duy nhất chứa hai số nguyên ~L, R~ (~1 \le L \le R \le 10^9~).

Output

• Dòng 1: số nguyên ~k~ là số số Kaprekar nằm trong đoạn ~[L, R]~.
• Dòng 2: ~k~ số nguyên là các số Kaprekar nằm trong đoạn ~[L, R]~, theo thứ tự tăng.

Sample Input 1

1 100

Sample Output 1

5
1 9 45 55 99

Sample Input 2

46 54

Sample Output 2

0

Subtasks

An có một bộ sưu tập đồ chơi gồm ~A~ món. Mỗi món đồ chơi thuộc về một trong ~T~ loại, các loại đồ chơi được đánh số từ 1 đến ~T~. An nhận ra rằng có thể tạo ra nhiều nhóm đồ chơi khác nhau bằng cách chọn một số món (có thể từ cùng một loại hoặc nhiều loại). Mỗi nhóm là một tập hợp không phân biệt thứ tự, nghĩa là hai nhóm được coi là khác nhau nếu tồn tại một loại đồ chơi có số lượng khác nhau trong hai nhóm.

Yêu cầu: Đếm số nhóm đồ chơi An có thể tạo ra có số lượng món không nhỏ hơn ~S~ và không lớn hơn ~B~. Trong một nhóm, số lượng đồ chơi của một loại nào đó không được lớn hơn số lượng thực tế An có. Kết quả lấy số dư trong phép chia cho 1,000,000.

Input

• Dòng đầu chứa 4 số nguyên: ~T, A, S, B~ — số loại đồ chơi, tổng số đồ chơi, giới hạn nhỏ nhất và lớn nhất số món trong một nhóm (~1 \le T \le 1000; 1 \le S \le B \le A~).
• ~A~ dòng tiếp theo, mỗi dòng chứa một số nguyên từ 1 đến ~T~ — biểu thị loại của từng món đồ chơi.

Output

Một dòng duy nhất là số nhóm đồ chơi có kích thước từ ~S~ đến ~B~, chia dư cho 1,000,000.

Sample Input 1

3 5 2 3
1
2
2
1
3

Sample Output 1

10

Subtasks