Mùa hè 2014, những người ngoài hành tinh đã có một chuyến viếng thăm trái đất. Họ đến bằng đĩa bay và đã chọn một cánh đồng của Việt Nam để hạ cánh. Đĩa bay có dạng hình tròn với \(N\) chân đế nên mỗi đĩa bay đã để lại trên cánh đồng một đường tròn với có \(N\) điểm trên đường tròn đó. Khi đĩa bay hạ xuống, các chân đế của một đĩa bay đã phát tia lazer để kết nối với nhau để lại các đường cháy trên cánh đồng. Ngay sáng hôm sau các nhà khoa học đã đến và dự đinh sẽ cắm tại mỗi giao điểm của các đường cháy bên trong mỗi đường tròn một lá cờ. Họ cũng phát hiện ra rằng, trong mỗi đường tròn không có 3 đường cháy nào cắt nhau tại cùng một điểm (trừ các điểm chân đế của đĩa
bay). Vấn đề đặt ra là với mỗi đường tròn, họ đã phải sử dụng bao nhiêu lá cờ. Các bạn hãy tính giúp các nhà khoa học nhé, đó chính là một con số quan trọng trong quá trình nghiên cứu sự hiện diện của người ngoài trái đất tại Việt Nam. In ra đáp số mod \(2014\).

Ví dụ, với hình bên là đĩa bay có \(5\) chân đế tương ứng với \(N=5\). Các đường cháy để lại giao nhau tại 5 điểm

Input

• Một dòng duy nhất chứa số \(N\) \((1 \le N \le 10^{16})\)

Example

7

35