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\%~ số test có ~N \le 17~;
• ~30\%~ số test khác có ~N \le 2 * 10^3~;
• ~10\%~ 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