Infinite string

Interview

Time limit2sMemory limit512 MB

Summary

Given two strings of length at most 50, decide whether each repeated infinitely produces the same infinite string.

Level: Medium4 of 10
Topics: String, String matching
Solved: No attempts yet

Problem

For a string $s$ , define $f(s)$ as the string obtained by concatenating $s$ infinitely many times. For example, if $s$ is abc, then $f(s)$ is abcabcabcabc....

Two different strings $s$ and $t$ can still give the same $f(s)$ and $f(t)$ . If $s$ is abc and $t$ is abcabc, then $f(s)$ and $f(t)$ are the same string.

Given $s$ and $t$ , write a program that decides whether $f(s)$ and $f(t)$ are the same string.

Input

The first line contains $s$ and the second line contains $t$ . The length of each string is a positive integer at most $50$ , and both strings consist of lowercase letters only.

Output

Print $1$ on the first line if $f(s)$ and $f(t)$ are the same, and $0$ otherwise.

Examples2

Example 1
Input
```
ab
abab
```
Expected output
```
1
```
Example 2
Input
```
abc
bca
```
Expected output
```
0
```