O(n) | Simple | C++
\nWe need to find the day we crossed n-1th room.\nWe need atleast 2 days to cross a room.\nThe number of days will be 2 when nextVisit[i] = i;\nElse if nextVisi
```\nWe need to find the day we crossed n-1th room.\nWe need atleast 2 days to cross a room.\nThe number of days will be 2 when nextVisit[i] = i;\nElse if nextVisit[i] = prev, then we will need prev->i + 2 days as we need to go back to prev\nand from there we again need to come to current room.\nSo maintain an array which tells us the day when we cross ith room.\nFor 0th room dp[0] = 2, as we can cross room 0 on day 2 and can visit room 1.\nSo for 1st room if dp[1]  = 1 then we can just add 2 to dp[0], dp[1] = dp[0] + 2;\nelse we need to go back to room given in 1 and add those days too.\nSo to generalize\ndp[i] = dp[i-1] + 2;\nif(nextVisit[i] != i) then dp[i] += days(nextVisit[i] -> i) and those days are from the day we\nentered nextVisit[i] (which is dp[nextVisit[i]-1]) till the day we entered i (which is dp[i-1])\n```\n```\ntypedef long long ll;\nclass Solution {\npublic:\n    ll M = 1e9+7;\n    int firstDayBeenInAllRooms(vector<int>& nextVisit) {\n        int n = nextVisit.size();\n        ll days[100001];\n        days[0] = 2;\n        for(int i=1; i<n-1; i++){\n            ll visit = nextVisit[i];\n            days[i] = days[i-1] + 2;\n            if(visit != i) days[i] += (M + days[i-1] - (visit > 0?days[visit-1]:0))%M;\n            days[i] %= M;\n        }\n        return days[n-2];\n    }\n};\n```
['Dynamic Programming', 'C']