We are given a string with the length of N, and the position containing "?" can be replaced by "a" or "B" or "C". Finally, how many subsequences of "ABC" can be obtained, and the modulus of its number is 100000007

First of all, let's consider the case that there is no "?" in the string. Define DP [s [J] — a '+ 1]] [J] to represent the contribution of the current character, and j to the position of the character in the string. For example, if the current character is "a", then DP [1] [J] = (DP [1] [J-1] + pre [CNT])% mods The pre array represents the contribution to "a" after the replacement of "?, which is equivalent to the conversion of"? Into three branches. Similarly, for DP [2] [J] = (DP [2] [J-1] + DP [1] [J-1])% mods represents the contribution made by the previous "a" when the current character is "B". Similarly, for the character "C", since "?" produces three branches, we have to multiply the contribution of "?" by 3
94214264 Please give me some advice if there is something wrong