神秘的孤胆英雄鸭，

正义的化身，

从阴影中飞出，

飞天德主宰着黑夜。

在某个角落，恶棍正在密谋，

但他的末日已到。

伴随着一团烟雾，他现身了，

惊喜的大师。

那阴影伪装背后，

是谁那狡黠的心智？

没人能确定，

但坏人们要倒霉了。

因为他来了——

飞天德！

—— 摘自迪士尼下午剧场系列《飞天德》

你真是受够这家伙了！他总是领先你一步，让你觉得有人专门写了个程序让他提前知道你的一举一动！你甚至有点后悔加入黑暗势力了。但现在你有一个计划。即使飞天德所在的城市无法抢劫，你仍然可以在郊区动手。这个郊区建在一条长街上，房屋用 ASCII 字符表示。

这里不再是飞天德的管辖范围，但有另一个守护者在此活动——GizmoDuck（机器鸭）。他是一只名叫 Ferton 的鸭子，穿着一套机器人装甲。有时 Ferton 只是在家里休息，街道仅由他的机器人装甲巡逻，由一个专门设计的程序控制。

该程序是一个由命令 'L' 和 'R' 组成的序列，机器人执行命令后会分别向左或向右移动一个房屋的距离。机器人的机械结构不允许它连续转向两次，因此禁止出现子串 "LRL" 和 "RLR"。此外，为了提高巡逻效率，在这些移动过程中，任何房屋被访问的次数都不能超过两次。

机器人会降落在某个房屋附近，执行命令序列，然后飞回家。他会准备一份完整的日志，其中按访问顺序记录了他访问过的所有房屋的标识（如果某个房屋被访问了两次，它在日志中也会出现两次）。

你发现了一串看起来像这种日志的字符，并且你还有一张郊区的地图。你想知道可能生成该日志的不同程序（由 "L" 和 "R" 组成的字符串）的总数。也许这能对你有所帮助。

输入格式

输入的第一行是一个非空字符串，由英文字母、数字以及符号 ,、;、:、?、. 和 - 组成，从左到右表示郊区中的房屋。

输入的第二行是一个非空字符串，由英文字母、数字以及符号 ,、;、:、?、. 和 - 组成，表示发现的日志。

每个字符串的长度不超过 $2 \cdot 10^5$ 个字符。

输出格式

输出一个整数：可以生成该日志的不同合法程序的总数。

样例

输入样例 1

Welcome_to_the_suburbia
rubu

输出样例 1

2

输入样例 2

aa
a

输出样例 2

1

说明

在第一个样例中，合法的程序是 "LLL" 和 "LLR"。机器人可以降落在位置 20（'b'），执行其中一个程序，并分别从位置 17 或 19 飞回家，从而生成预期的日志。

在第二个样例中，唯一可能的程序是空字符串（它可以从任何降落位置执行）。