There are n rooms labeled from $0$ to n $- 1$. Starting on day $0$, you begin in room $0$ and visit one room each day.

You are given a $0$ indexed integer array nextVisit of length n. When you are in room i on any day:

• If you have visited room i an odd number of times (including the current visit), the next room you visit will be nextVisit[i].

• If you have visited room i an even number of times (including the current visit), the next room you visit will be (i + 1) % n.

Return the first day on which you have visited every room at least once. Since the answer may be very large, return it modulo $10^9 + 7$.

Constraints:

• n == nextVisit.length

• $2 \leq$ n $\leq 10^5$

• $0 \leq$ nextVisit[i] $\leq$ i

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.