n rooms numbered 0 to n - 1. Each day he enters exactly one room; days are numbered from zero, and on day 0 he is in room 0.
Where he goes next is decided by an array back_to of length n. Say he is in room i today:
- if he has now been in that room an **odd** number of times (today's visit included), tomorrow he goes to room back_to[i], where 0 ≤ back_to[i] ≤ i;
- if the count is **even**, tomorrow he goes to room (i + 1) mod n.
Return the first day by which the guard has been in every room. Such a day always comes. The answer can be huge, so return it modulo 10⁹ + 7.back_to=[0, 1] → 2
Day 0: room 0, first visit (odd), so go back to back_to[0] = 0. Day 1: room 0 again, second visit (even), so move on. Day 2: room 1, and every room has been seen.
back_to=[0, 1, 1] → 4
The rooms by day are 0, 0, 1, 1, 2, so the guard first reaches room 2 on day 4.
back_to=[0, 0, 0] → 6
The order is 0, 0, 1, 0, 0, 1, 2: each odd visit to room 1 throws the guard back to the start, so the answer is 6.
back_to=[0, 1]
2
Run checks the first 3 tests in your browser. Submit checks all 72 tests on the server, hidden ones included.