J1 例题-10 汪星人密电

题目描述

情报科科长小喵截取了一段汪星人侵略者的情报密电，是一段仅由 D,O,G,X 组成的字符序列。为了保卫喵星的和平，免受汪星人的侵略，小喵要破解这段密电。 经过仔细的研究，小喵发现密电中每出现一个 DOG 子序列（不需要连续，但顺序不能颠倒），就代表汪星人将排遣一支侵略军来袭。 请帮助小喵破解密电，确定汪星人将排遣多少支侵略军！

输入格式

一行一串字符序列，仅由 D,O,G,X 组成。

输出格式

一行一个整数，输出汪星人将排遣多少支侵略军（DOG子序列的数量）； 其中 DOG 必须为正序，OGD、GOD、DGO、ODG 等都不合法。

样例输入

DOGGODXG

样例输出1

4

样例解析

子序列的组成如下图：

数据范围

对于 $100\%$ 的数据：字符串长度 $\le 2000$ 。