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 ;