{"problem":{"name":"SSttrriinngg in StringString","description":{"content":"For a string $X$ of length $n$, let $f(X,k)$ denote the string obtained by repeating $k$ times the string $X$, and $g(X,k)$ denote the string obtained by repeating $k$ times the first character, the s","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc346_f"},"statements":[{"statement_type":"Markdown","content":"For a string $X$ of length $n$, let $f(X,k)$ denote the string obtained by repeating $k$ times the string $X$, and $g(X,k)$ denote the string obtained by repeating $k$ times the first character, the second character, $\\dots$, the $n$\\-th character of $X$, in this order. For example, if $X=$ `abc`, then $f(X,2)=$ `abcabc`, and $g(X,3)=$ `aaabbbccc`. Also, for any string $X$, both $f(X,0)$ and $g(X,0)$ are empty strings.\nYou are given a positive integer $N$ and strings $S$ and $T$. Find the largest non-negative integer $k$ such that $g(T,k)$ is a (not necessarily contiguous) subsequence of $f(S,N)$. Note that $g(T,0)$ is always a subsequence of $f(S,N)$ by definition.\nWhat is a subsequence? A (not necessarily contiguous) subsequence of a string $X$ is a string obtained by removing zero or more characters from $X$ and then concatenating the remaining elements without changing the order. For example, `ac`, `atcoder`, and (empty string) are all subsequences of `atcoder`, but `ta` is not.\n\n## Constraints\n\n*   $N$ is an integer.\n*   $1\\leq N\\leq 10^{12}$\n*   $S$ and $T$ are strings consisting of lowercase English letters with lengths between $1$ and $10^5$, inclusive.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$S$\n$T$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc346_f","tags":[],"sample_group":[["3\nabc\nab","2\n\nWe have $f(S,3)=$ `abcabcabc`. $g(T,2)=$ `aabb` is a subsequence of $f(S,3)$, but $g(T,3)=$ `aaabbb` is not, so print $2$."],["3\nabc\narc","0"],["1000000000000\nkzazkakxkk\nazakxk","344827586207"]],"created_at":"2026-03-03 11:01:14"}}