Problem Background

Cirno wants to decipher an ancient magical book.

Problem Description

To protect the forbidden magic recorded in the book, the author connected the magical suffixes of the runes without spaces, forming a rune string, denoted as $\texttt{S}$.

All the magical suffixes that make up the rune string are recorded in a magical dictionary compiled by ancient prophets, denoted as $\texttt{T}$. Specifically, all non-empty prefixes of $\texttt{T}$ are valid magical suffixes.

Simplicity is the foremost priority in the writing of magical books, so the number of magical suffixes used should be as few as possible. Therefore, when deciphering the magical book, the fewer the number of magical suffixes into which $\texttt{S}$ is divided, the higher the likelihood of correct deciphering.

Cirno wants to know the minimum number of magical suffixes into which this magical book can be divided.

Specifically, if there is no valid division scheme, it indicates that the magical book is fake. Cirno will get a string Fake.

Input Format

The first line contains two integers, representing $|\texttt{T}|$ and $|\texttt{S}|$.

The second line contains a string $\texttt{T}$.

The third line contains a string $\texttt{S}$.

Output Format

One line, an integer or a string Fake, representing the answer.

Sample Input and Output

Sample Input #1

3 5
aba
abaab

Sample Output #1

2

Sample Input #2

3 5
aba
ababa

Sample Output #2

2

Sample Input #3

3 5
aba
abbaa

Sample Output #3

Fake

Notes

Data Range and Constraints

For $100\%$ of the data, it is guaranteed that $1 \le |\texttt{S}|, |\texttt{T}| \le 10^7$, and $\texttt{S}_x, \texttt{T}_x \in [\texttt{a}, \texttt{z}]$.

Subtasks

Subtask1 ($10$ points): $\texttt{T}_x = \texttt{a}$.

Subtask2 ($20$ points): $|\texttt{S}| \le 1000$.

Subtask3 ($30$ points): $|\texttt{S}| \le 10^6$.

Subtask4 ($40$ points): No special restrictions.

见题面 Input 部分

见题面 Output 部分