Average Curses of Arcane Gems

Deep within the plots of the Earth Disaster Legion, the tactician in black robes learned from a spy in the elven high council about the legendary Arcane Scepter. Intrigued by the primeval magic hidden in the Arcane Gems, he designed a scheme to seize several of them. As the chief scientist, you are assigned to lead research in deciphering their internal energy structures.

The gem cores come in two types. The Type‑2 Arcane Gem has each of its k reaction cores in the form of a 2×n grid, and the Type‑3 Arcane Gem has each core as a 3×n grid (note that the number of cores k and the length n may differ).

When the magical reaction happens, each core is fully filled with magical particles. Each particle is a domino tile of size 1×2 that can be placed either horizontally or vertically; a tiling of a core is valid if every cell of the grid is covered exactly once. Two tiling schemes for a grid are considered different if there exists at least one cell that is covered by a domino in a different position or orientation. For example, a 2×4 grid has 5 tiling schemes, and a 3×2 grid has 3 tiling schemes.

A powerful curse is created only if the tiling patterns chosen for the k cores are all distinct. In other words, two curse combinations are regarded as identical if for every tiling in the first combination there exists a tiling in the second combination that is exactly the same.

Formally, for a Type‑2 Arcane Gem with width n and k cores, let the number of different curses be

$$F(n,k)=\binom{T_{2}(n)}{k},$$

where \(T_{2}(n)\) is the number of tiling schemes for a 2×n grid. Similarly, for a Type‑3 Arcane Gem, if \(T_{3}(n)\) denotes the number of tiling schemes for a 3×n grid (note that \(T_{3}(n)=0\) when \(n\) is odd), then the number of curses is

$$G(n,k)=\binom{T_{3}(n)}{k}.$$

For example, \(F(4,1)=5\), \(F(4,2)=10\) and \(G(2,2)=3\).

The exact width n of the cores cannot be measured accurately – only an approximate range \([l,r]\) is known. You are to compute the average number of curses for cores with lengths in this interval:

$$ans2 = \frac{1}{r-l+1}\sum_{n=l}^{r} F(n,k), \quad ans3 = \frac{1}{r-l+1}\sum_{n=l}^{r} G(n,k). $$

The final answer should be expressed as a reduced fraction \(\frac{A}{B}\). Output the value of \(A\times B^{-1} \bmod 998244353\), where \(B^{-1}\) is the multiplicative inverse of \(B\) modulo 998244353.

Note: The tiling number for a 2×n grid is the \((n+1)\)th Fibonacci number with initial values 1 and 2 (i.e. 2×1 grid has 1 tiling, 2×2 grid has 2 tilings, 2×3 grid has 3 tilings, etc.), and the tiling number for a 3×n grid (when \(n\) is even) can be computed by the recurrence

$$a(0)=1,\quad a(1)=3,\quad a(m)=4\,a(m-1)-a(m-2)\text{ for }m\ge2,\quad \text{with }n=2m. $$

inputFormat

The input consists of three space‐separated integers:

• l and r (\(1 \le l \le r\)) that denote the inclusive range for the core length n.
• An integer k (\(k \ge 1\)) denoting the number of cores.

outputFormat

Output two integers separated by a space: the value of \(ans2\) and \(ans3\) modulo 998244353.

sample

4 4 1

5 11