Đảo chiều đường

Cho một đất nước có $n$ thị trấn được đánh số từ $1$ đến $n$ và đúng $n$ con đường một chiều. Con đường thứ $i$ đi từ thị trấn $i$ đến thị trấn $a_i$ (với $a_i\ne i$).

Bạn được phép chọn một tập con bất kỳ trong các con đường rồi đảo chiều mỗi con đường trong tập đó đúng một lần (con đường $A\to B$ trở thành $B\to A$).

Mạng đường được gọi là rối nếu sau khi đảo chiều tồn tại một dãy các thị trấn phân biệt $A_1,A_2,\dots ,A_k$ ($k>1$) sao cho có đường từ $A_i$ đến $A_{i+1}$ với mọi $1\le i<k$ và có đường từ $A_k$ về $A_1$ — nói cách khác, mạng có chứa một chu trình có hướng.

Hãy đếm số tập con của các con đường (trong tổng cộng $2^n$ tập con) mà sau khi đảo chiều mỗi con đường trong tập đó, mạng đường thu được không bị rối. In ra kết quả theo modulo ${10}^9+7$.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên $n$ — số thị trấn.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ — $a_i$ là đích đến của con đường xuất phát từ thị trấn $i$.

Dữ liệu ra

In ra một số nguyên duy nhất là số tập con cần đếm, lấy modulo ${10}^9+7$.

Ràng buộc

• $2\le n\le 2·{10}^5$
• $1\le a_i\le n$, $a_i\ne i$

Ví dụ