Parent’s love is eternal and so is the love for parents. In this fast moving world, we often forget to show our love and call "MOM" and "DAD". It is time to recall them as many times as possible in this challenge. In this challenge, you are given a string S and you have to determine the count of subsequences of "DAD" and "MOM" in the given string.
Note: The order of the sequence should be the same however letters don’t have to be consecutive.
The only line of input consists of a string.
It is guaranteed that the string consists of only uppercase English letters.
1<= |S| <=100000
Print a single integer – the number of subsequences "DAD" and "MOM" in the string.
Sample TestCase 1
There are 4 subsequences of MOM and 3 subsequences of DAD in the given string.
0.50 SEC(S) FOR EACH INPUT.
C, C++, C++11, C++14, C#, JAVA, JAVA 8, KOTLIN, PHP, PHP 7, PYTHON, PYTHON 3, PERL, RUBY, NODE JS, SCALA, CLOJURE, HASKELL, LUA, ERLANG, SWIFT, VBNET, JS, OBJC, PASCAL, GO, F#, D, GROOVY, TCL, OCAML, SMALLTALK, COBOL, RACKET, BASH, GNU OCTAVE, RUST, COMMON LISP, R, JULIA, FORTRAN, ADA, PROLOG, ICON, ELIXIR, COFFEESCRIPT, BRAINFUCK, PYPY, LOLCODE, NIM, PICOLISP, PIKE, WHITESPACE, PYPY3
Source: Windows Questions C++