A and B 2

Interview

Time limit2sMemory limit512 MB

Summary

Given two strings of A and B, decide whether repeatedly appending A or appending B then reversing can turn S into T.

Level: Medium5 of 10
Topics: String, Greedy, Implementation, Recursion
Solved: No attempts yet

Problem

Subin was surprised that some English words are spelled with only the letters A and B. AB (short for Abdominal), BAA (the cry of a sheep), AA (a type of lava), and ABBA (the Swedish pop group) are such words.

Subin turned that into a simple game. You are given two strings S and T, and the goal is to turn S into T. Only these two operations are allowed.

Append A to the end of the string.
Append B to the end of the string, then reverse the whole string.

Write a program that decides whether applying the two operations any number of times, in any order, can turn S into T.

Input

The first line contains S and the second line contains T. Both strings consist only of A and B.

$1 \le |S| \le 49$ , $2 \le |T| \le 50$ , and $|S| < |T|$ .

Output

Print 1 if S can be turned into T, and 0 if it cannot.

Examples3

Example 1
Input
```
A
BABA
```
Expected output
```
1
```
Example 2
Input
```
BAAAAABAA
BAABAAAAAB
```
Expected output
```
1
```
Example 3
Input
```
A
ABBA
```
Expected output
```
0
```