Python prefix sum DP solution, with explanation
There are two keypoints to approach this problem:\n When first visiting the room i+1, the room i is visited twice. One visit comes from "the first visit to room
There are two keypoints to approach this problem:\n* When first visiting the room i+1, the room i is visited twice. One visit comes from "the first visit to room i", the second visit comes from "additional steps to visit room i again".\n* The next day after we first visit room i, we will visit room (nextVisit[i]). The problem turns into "how to go from room (nextVisit[i]) to room i".  \n```\nclass Solution:\n    def firstDayBeenInAllRooms(self, nextVisit: List[int]) -> int:\n\t        n:int = len(nextVisit)\n        days:List[int] = n*[0] # days[i] is the number of days it takes to first reach room i\n        MOD = pow(10, 9) + 7\n        for i in range(0,n-1):\n            # First we are already at room i. days[i] days has passed\n            days[i+1] = days[i]\n            # lets go from room i to room i+1. \n            # When we first visit room i, we need to visit room i again (so room i is visited twice, which is an even number), then we can visit room i+1\n            # after we fist visit room i, the next day we will visit room (nextVisit[i]). \n            days[i+1] = (days[i+1] + 1) % MOD\n            # Then the problem becomes "how to go from room (nextVisit[i]) back to room i". The step is (days[i] - days[nextVisit[i]])\n            days[i+1] = (days[i+1] + days[i] - days[nextVisit[i]]) % MOD\n            # Then, in the next day we go from room i to i+1\n            days[i+1] = (days[i+1] + 1) % MOD\n        \n        return days[n-1]\n```
['Dynamic Programming', 'Prefix Sum', 'Python']