Description

The boy only has one string $S$, with length $n$, indexed from $1 \dots n$;
and an array $a_{1\dots n}$.

The boy wrote down two numbers $L, R$ and tried to find those shards that have been lit by light:
For two substrings $(S_{l_1\dots r_1}, S_{l_2\dots r_2})$ in $S$ that occur at different positions but are identical in content, if $L \le (a_{r_1} \oplus a_{r_2}) + (r_1 - l_1 + 1) \le R$, then there is light between these two substrings.
Here, $S_{l\dots r}$ denotes the substring formed by concatenating the characters of $S$ with indices in $[l, r]$ in order, and $\oplus$ denotes the bitwise XOR operation.

The boy wants to know how many pairs of substrings have light between them.
Substring pairs are unordered. Specifically, $(S_{l_1\dots r_1}, S_{l_2\dots r_2})$ and $(S_{l_2\dots r_2}, S_{l_1\dots r_1})$ are considered the same pair.
You only need to output the answer modulo $998244353$.

Input Format

The first line contains a positive integer $n$.
The second line contains a string $S$.
The third line contains $n$ non-negative integers $a_{1\dots n}$.
The fourth line contains two non-negative integers $L, R$.

Output Format

One line containing a non-negative integer, which is the answer.

5
abcbc
0 1 2 3 4
2 7

2

Hint

Constraints:
For $20\%$ of the testdata, $n \le 100$;
For $50\%$ of the testdata, $n \le 10^3$;
For $100\%$ of the testdata, $1 \le n \le 10^5$, $0 \le a_i, L, R \le 10^5$, $L \le R$, and $S$ contains only lowercase letters.

"A gift from the problem setter"
Be a bit braver. Trust the constant factor of some algorithm. What you think of might be a trash standard solution.

Translated by ChatGPT 5