Cho một số nguyên dương $N$. Tính tổng của $N$ số chính phương đầu tiên.

Input

Gồm một số nguyên dương $N$ $(N\le {10}^{10})$.

Output

In ra phần dư của tổng tìm được cho 2021.

Ràng buộc

• Có $60\mathrm{\%}$ số test có $N\le 17$;
• $30\mathrm{\%}$ số test khác có $N\le 2\ast {10}^3$;
• $10\mathrm{\%}$ số test còn lại không có ràng buộc gì thêm.

Sample Test 1

Input

4

Output

30

Sample Test 2

Input

20

Output

849

Dino đang học về các con số. Bố cho Dino $a_0$ chữ số $0$; $a_1$ chữ số $1$; ...; $a_9$ chữ số $9$. Bố hỏi Dino có thể ghép được nhiều nhất bao nhiêu số tự nhiên liên tiếp từ $N$ trở đi. Bạn hãy lập trình giúp Dino kiểm tra xem.

Input

• Dòng đầu tiên chứa số nguyên dương $N$ $(N\le {10}^9)$;
• Dòng thứ hai chứa 10 số nguyên mô tả số lượng các chữ số từ $0$ đến $9$: $a_0,a_1,...,a_9$ $(0\le a_i\le {10}^{11})$.

  Output

Số lượng số mà Dino ghép được nhiều nhất thoả mãn đề bài.

Sample Test 1

Input

12
0 4 2 1 1 1 3 0 0 0

Output

4

Giải thích: Ghép được thành $4$ số: $12,13,14,15$. Không ghép được thành $16$ vì không đủ chữ số $1$.

Sample Test 2

Input

103
9 4 2 0 1 1 3 0 0 0

Output

0