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

I told me that I love you, not necessarily with you, just hope that in the future, when you encounter a low life, don't lose heart, at least someone was attracted by your charm, once was, will be, if like is the paranoia that wants to possess, then love is the restraint that wants to touch but take back the hand. I don't expect to be able to stand by you one day Side, I just want you to know, your light, once illuminated me