本题考察线性dp，考虑一个递推做法

$dp[i][0]$ 表示 前 $i$ 个字符，不管如何改变*, 可能产生的 S的个数

$dp[i][1]$ 表示 前 $i$ 个字符，不管如何改变*, 可能产生的 SO的个数

$dp[i][2]$ 表示 前 $i$ 个字符，不管如何改变*, 可能产生的 SOS的个数

那么考虑当前位置$i$ 是 *

对于转移，这个位置可以是O 也可以是 S, 那么

$dp[i][0] = (dp[i - 1][0] \times 2 \% mod + 2^{前面*号的个数}) \% mod;$ 因为如果变成 S, 那么前面可以通过改变*对答案的贡献就是 $2^{前面*号的个数}$

$dp[i][1] = (dp[i - 1][1] \times 2 \% mod + dp[i - 1][0]) \% mod;$

$dp[i][2] = (dp[i - 1][2] \times 2 \% mod + dp[i - 1][1]) \% mod;$

那么考虑当前位置$i$ 是 S 或者 O 时的转移留给同学们思考。