Prefix sum of number of substrings whose sum of digits mudolo 3 is 0 , 1 , 2.
dp [ i ] [ 0 ] = dp [ i - 1 ] [ 0 ] ; dp [ i ] [ 1 ] = dp [ i - 1 ] [ 1 ] ; dp [ i ] [ 2 ] = dp [ i - 1 ] [ 2 ] ; dp [ i ] [ sum [ i ] ] ++ ; } int ans = 0 , dprev = 0 , value = 0 , dprev2 = 0 ;