Phân tích hàm băm

Sau cuộc tấn công tàn khốc của các cỗ máy, dự án YoRHa mới quyết định triển khai một hệ thống an ninh tối tân. Hệ thống này sử dụng các thuật toán mã hóa tiên tiến để đảm bảo thông tin quan trọng luôn được bảo mật. Trọng tâm của hệ thống an ninh này là một cơ chế băm độc đáo, trong đó mỗi mẩu dữ liệu được biểu diễn bằng phép toán toán học \(x^y \pmod{p}\), với \(p\) là một số nguyên tố. Hệ thống này biến đổi mọi đầu vào thành một "chữ ký", một chuỗi dường như ngẫu nhiên mà chỉ các máy chủ của YoRHa mới có thể giải mã.

Tuy nhiên, khi cuộc chiến với các cỗ máy kéo dài, các nhà điều hành bắt đầu lo ngại. Điều gì sẽ xảy ra nếu nhiều mẩu thông tin khác nhau, khi được xử lý bởi thuật toán băm này, lại tạo ra cùng một chữ ký? Điều này có thể dẫn đến một thất bại thảm khốc trong hệ thống an ninh, khi dữ liệu quan trọng bị ghi đè hoặc mất do các vụ "va chạm" trong hàm băm. Để ngăn chặn điều này, nhà điều hành 21O được giao một nhiệm vụ quan trọng: tính toán xem có bao nhiêu đầu vào khác nhau có thể băm thành cùng một chữ ký, cho mọi kết quả đầu ra có thể.

Với mỗi \(k = 1, 2, 3, \ldots, p-1\), nhà điều hành phải phân tích có bao nhiêu cặp số nguyên \((a, b)\) với \(1 \le a, b \le p-1\) thỏa mãn \(a^b \equiv k \pmod{p}\). Bằng cách xác định có bao nhiêu tổ hợp khác nhau tạo ra cùng một kết quả băm, họ có thể đánh giá rủi ro va chạm và điều chỉnh các giao thức an ninh cho phù hợp. Cuộc phân tích này trở thành một cuộc chạy đua với thời gian, vì sự toàn vẹn của hệ thống liên lạc và lưu trữ dữ liệu của YoRHa phụ thuộc vào việc thực hiện thành công nhiệm vụ này. Vận mệnh của cuộc chiến có thể phụ thuộc vào khả năng của nhà điều hành trong việc đảm bảo hệ thống an ninh luôn bất khả xâm phạm.

Input

• Một số nguyên duy nhất \(p\) (\(2 \le p < 100,000\)). Đảm bảo rằng \(p\) là một số nguyên tố.

Output

• Một dòng duy nhất chứa \(p-1\) số nguyên. Số thứ \(k\) là số cặp \((a, b)\) thỏa mãn \(a^b \equiv k \pmod{p}\).

Example

3

3 1 

13

40 4 16 8 10 4 4 10 16 8 4 20 

Scoring

• Subtask 1 (30 điểm): \(p \le 500\).
• Subtask 2 (30 điểm): \(p \le 10000\).
• Subtask 3 (40 điểm): Không có ràng buộc gì thêm.