module Main where

import Data.List (subsequences)

main :: IO ()
main = interact $ show . f . readABCs . head . lines

data ABC
  = A
  | B
  | C
  deriving (Show, Eq)

f :: [[ABC]] -> Int
-- f xss = length . (filter ([A, B, C] ==)) $ subsequences =<< xss
f xss = length . (filter ([A, B, C] ==)) $ combinations 3 =<< xss

readABCs :: String -> [[ABC]]
readABCs "" = [[]]
readABCs ('A' : cs) = map (A:) $ readABCs cs
readABCs ('B' : cs) = map (B:) $ readABCs cs
readABCs ('C' : cs) = map (C:) $ readABCs cs
readABCs ('?' : cs) = (:) <$> [A, B, C] <*> readABCs cs
readABCs _ = error "readABCs: parse error"

tests :: [Bool]
tests = [test1, test2]

test1, test2 :: Bool
test1 = f (readABCs "A??C") == 8
test2 = f (readABCs "ABCBC") == 3
test3 = f (readABCs "????C?????B??????A???????") == 979596887

combinations :: Int -> [a] -> [[a]]
combinations 0 _ = [[]]
combinations _ [] = []
combinations m xxs@(x : xs) = map (x:) (combinations (m - 1) xs) ++ combinations m xs
