형제와 자매

진송과 진희는 남매다. 두 사람은 같은 대학교에 다닌다. 진송은 ICPC 훈련 동아리 회원이고, 진희는 영어 동아리 회원이다.

오늘은 진희의 열일곱 번째 생일이고, 동시에 대학교에서 맞는 첫 생일이다. 그래서 좋은 오빠인 진송은 예쁜 여동생을 위해 멋진 선물을 준비했다. 그런데 장난꾸러기 여동생은 진송이 일어나기 전에 학교로 가 버렸고, 진송은 영어 동아리로 가서 생일 선물을 주기로 했다.

진희는 아주 영리한 아이라 오빠가 분명히 자기를 보러 올 것이라고 생각하고, 오빠에게 재미있는 장난을 준비하기로 했다. 영어 동아리에는 진희의 동료가 $n$명 있고, 모두 진희의 생각에 동의했다. 먼저 진희는 자기와 동료들에게 번호를 붙였다. 진희는 $0$번이고, 동료들은 $1$부터 $n$까지 서로 다른 정수로 번호가 매겨진다. 그다음 동료들에게 자기와 똑같은 교복과 두꺼운 안경을 착용하게 해서 $n + 1$명의 여학생이 완전히 똑같아 보이게 만들었다. 그 결과 진송은 혼란스러워하며 여동생을 찾으려 할 것이다. 장난은 다음과 같이 진행된다.

1. 진송은 아직 물어보지 않은 여학생 $i$를 무작위로 균등하게 고른다.
2. 고른 여학생에게 "너는 내 여동생이니?"라고 묻는다. 지금 고른 여학생 $i$가 진희라면(즉 $i = 0$), 진희는 즉시 장난을 끝낸다. 그렇지 않으면 여학생 $i$는 진희가 $p\_i$번 여학생이라고 말한다. $p\_i$ 값은 진송이 오기 전에 미리 정해 둔다.
3. $p\_i = i$라면(즉 동료가 자기 자신이 진희라고 말한다면), 또는 진송이 이미 $p\_i$번 여학생에게 물어봤다면, 진송은 그 여학생이 거짓말을 했다는 것을 알아차리고 1단계로 간다. 그렇지 않으면 $p\_i$번 여학생에게 계속 물어보며 2단계로 간다.

진송은 여동생을 최대한 빨리 찾고 싶어 하고, 영리한 여동생을 찾는 데 얼마나 걸릴지 알고 싶어 한다.

여러분의 과제는 장난이 끝날 때까지 진송이 물어봐야 하는 여학생 수(여동생 포함)의 기댓값을 구하는 것이다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다 ($1 \le T \le 10$).

각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에 진희의 동료 수 $n$이 주어진다 ($1 \le n \le 10^5$). 둘째 줄에 $n$개의 정수 $p\_1, p\_2, \ldots, p\_n$이 공백으로 구분되어 주어진다. $p\_i$는 동료 $i$가 진송을 보내는 동료의 번호다 ($1 \le p\_i \le n$).

기댓값은 $p / q$ 꼴의 기약분수로 나타낼 수 있음이 보장된다(즉 $p$와 $q$는 서로소인 정수다). 따라서 각 테스트 케이스마다 한 줄에 정수 $(p \cdot q^{-1}) \bmod (10^9 + 7)$을 출력한다.

예시에서 첫 번째 여학생을 고르는 방법은 4가지다. 그리고 진송이 첫 번째 여학생을 고른 뒤에 벌어지는 일은 유일하게 결정된다. 한 가지는 여동생을 먼저 고르는 것이고, 나머지는 1, 2, 3을 고르는 것이다.

여동생을 먼저 고르면 장난이 즉시 끝나고, 모두 1명의 여학생에게 물어본다.

1번 여학생을 먼저 고르면 1, 2, 3번 여학생에게 물어본다. 그러고 나서 그들이 거짓말을 했다는 것을 알아차리고 곧바로 여동생에게 간다. 따라서 $1, 2, 3, 0$ 순서로 모두 4명의 여학생에게 물어본다.

2번이나 3번 여학생을 먼저 고르는 경우도 1번을 고르는 경우와 비슷하다. 여학생의 순서는 각각 $2, 3, 1, 0$과 $3, 1, 2, 0$이다.

각 경우는 모두 $1 / 4$의 같은 확률로 일어난다.

따라서 답은 $((1 + 4 + 4 + 4) \cdot 4^{-1}) \bmod (10^9 + 7) = 250\,000\,005$이다.