This question was featured in a ICPC Regional Contest. It gives a string of 'I' (increasing), 'D' (decreasing) and/or '?' (either increasing or decreasing) to represent two consecutive members of an n-permutation. ex. IID can be {1,2,4,3} or {2,3,4,1} etc. Your task is given a string, find the number of possible permutations that fit the string in mod 10^9 + 7.

A working solution is found here. Can someone please clarify the recurrence relation to solve this dp?