A and B

Interview

Time limit2sMemory limit512 MB

Summary

Given two strings of A and B, decide whether S can be turned into T using only: append A, or reverse then append B.

Level: Medium6 of 10
Topics: Greedy, String, Implementation, Simulation
Solved: No attempts yet

Problem

Subin was surprised to learn that some English words use only the letters A and B. AB (short for Abdominal), BAA (the sound a sheep makes), AA (a type of lava), and ABBA (the Swedish pop group) are examples.

Starting from that idea, Subin made a simple game. Given two strings $S$ and $T$ , the goal is to turn $S$ into $T$ . Only these two operations can change a string.

Append A to the end of the string.
Reverse the string, then append B to the end.

Write a program that decides whether these operations can turn $S$ into $T$ .

Input

The first line contains $S$ and the second line contains $T$ . Both strings consist only of the uppercase letters A and B. ( $1 \le |S| \le 999$ , $2 \le |T| \le 1000$ , $|S| < |T|$ )

Output

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

Examples2

Example 1
Input
```
B
ABBA
```
Expected output
```
1
```
Example 2
Input
```
AB
ABB
```
Expected output
```
0
```