Problem : 300 - Party Invitation

Problem Statistics

Solved Member: 5　　Submission: 12　　User Tried: 5

Statement:

瀚瀚有 n 位碰友，分別以 1,2,3,...,n 來編號。他今天想要邀請一些人來家裡一起7122。

然而，對於每一個碰友 i，會有一個特定討厭的碰友 a_i，代表瀚瀚不能同時邀請 i 與 a_i 兩個人，否則他們會打架，瀚瀚就7122不出來了。

請你找出瀚瀚有幾種邀請碰友的方法。

Input:Output:

輸入資料的第一行有一個整數 t，代表測資的筆數。

每一筆測試資料的第一行有一個整數 n，代表瀚瀚的好友數量。
接下來有 n 個數字 a₁, a₂, ..., a_n，分別代表每個人討厭的人的編號。

限制：
t ≤ 10
2 ≤ n ≤ 100000
i ≠ a_i (沒有人會討厭自己)

其中 30% 的測試資料滿足： n ≤ 20
其中 70% 的測試資料滿足： n ≤ 2000

對於每一筆測試資料，請輸出一行，包含一個數字，代表瀚瀚有幾種邀請別人來7122的方法。
由於方法數可能很大，請輸出除以 1000000007 的餘數。

Sample Input:Sample Output:

3
4
2 3 4 1
3
2 1 2
2
2 1

7
5
3

HINT:

我們用 {...} 來表示邀請到哪些人。

第一筆測試資料，瀚瀚可以邀請的可能為：{}, {1}, {2}, {3}, {4}, {1,3}, {2,4}，共七種

第二筆測試資料，瀚瀚可以邀請的可能為：{}, {1}, {2}, {3}, {1,3}

第三筆測試資料，瀚瀚可以邀請的可能為：{}, {1}, {2}

Source:

Codechef

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	2000ms	131072kb
1	2000ms	131072kb	10
2	2000ms	131072kb	10
3	2000ms	131072kb	10
4	2000ms	131072kb	10
5	2000ms	131072kb	10
6	2000ms	131072kb	10
7	2000ms	131072kb	10
8	2000ms	131072kb	10
9	2000ms	131072kb	10
10	2000ms	131072kb	10