A tree $T = (V, E)$ is an undirected connected simple graph without cycles. In this problem, we consider $c$-colored trees, which are trees where each vertex is colored with one of $c$ colors.

Two colored trees $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$ are equal if: there exists a bijection $\pi : V_1 \to V_2$ such that for every pair of vertices $u, v \in V_1$, the relation $\{u, v\} \in E_1$ holds if and only if $\{\pi(u), \pi(v)\} \in E_2$; and for every vertex $v \in V_1$, the color assigned to $v$ in tree $T_1$ is the same as the color assigned to vertex $\pi(v)$ in tree $T_2$.

An independent set in a tree $T = (V, E)$ is any subset of vertices $S \subseteq V$ such that no two distinct vertices belonging to $S$ are connected by an edge. The size of an independent set $S$ is the number of vertices belonging to $S$.

You are given three numbers $\ell$, $r$, and $c$. How many different $c$-colored trees exist whose maximum independent set has a size of at least $\ell$ and at most $r$? Since the result can be very large, provide only its remainder when divided by $998\,244\,353$.

Input

The first and only line of input contains three integers $\ell$, $r$, and $c$ ($1 \le \ell \le r \le 500\,000$, $1 \le c \le 998\,244\,352$).

Output

In the first and only line of output, provide a single number: the remainder when dividing the total number of different $c$-colored trees whose maximum independent set has a size in the range $[\ell, r]$ by $998\,244\,353$.

Examples

Input 1

1 3 1

Output 1

9

Input 2

1 3 2

Output 2

149

Note

Explanation of the first example: all different 1-colored trees with a maximum independent set of size 1, 2, or 3 are shown below:

Subtasks

In some test groups, the condition $\ell = r$ holds. Furthermore, in some (possibly different) test groups, the condition $c = 1$ holds.