我的世界建筑师

题目描述

在一个在线的游戏开发者论坛上，一个知名的游戏管理员因为沉迷于玩《我的世界》并在论坛中分享大量建筑技巧，经常在游戏开发中出现失误。他现在给你一个长字符串 $string$，他希望你帮忙统计有多少种方式可以从字符串 $string$ 中找出两个特定的子串：

• 第一个子串 $string[l_1, r_1]$ 必须是 "Minecraft"。
• 第二个子串 $string[l_2, r_2]$ 必须是 "builder"。
• 并且要满足 $1 \leq l_1 \leq r_1 < l_2 \leq r_2 \leq |string|$，这里 $|string|$ 表示字符串 $string$ 的长度。

你需要计算所有这样的有效配对。

输入格式

输入只包含一行，即字符串 $string$。

输出格式

输出一个整数，表示符合条件的子串对的总数。

样例 #1

输入

Minecraftbuilderbuilder

输出

2

样例 #2

输入

MinecraftIstringbuilderAFunGameWithMinecraftWhoLikestringToBeAMinecraftbuilder

输出

4

数据范围

• 对 $30\%$ 的数据，保证 $|string| \leq 50$。
• 对 $60\%$ 的数据，保证 $|string| \leq 500$。
• 对 $100\%$ 的数据，保证 $1 \leq |string| \leq 2000$，$string$ 中仅含大小写英文字母。