Cho một bảng hình vuông kích thước n × n được chia thành lưới ô vuông đơn vị, các vị trí đỉnh của các ô vuông đơn vị được gọi là các mắt lưới. Hãy đếm số lượng hình vuông thỏa mãn hai điều kiện:

• Mỗi cạnh của hình vuông song song với một cạnh của bảng.

• Cả bốn đỉnh của hình vuông nằm tại các mắt lưới.

Ví dụ với bảng 3 × 3 có thể đếm được 14 hình vuông thỏa mãn hai điều kiện trên.

Yêu cầu

Do số lượng hình vuông có thể rất lớn, hãy in kết quả theo modulo 2013.

Input

Một số nguyên dương n (n ≤ 10¹⁸).

Output

Một số nguyên: số lượng hình vuông tìm được, lấy theo modulo 2013.

Ví dụ

Input

3

Output

14