L. La Vaca Saturno Saturnita vs Tung Tung Tung Sahur
time limit per test
0.25 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

La Vaca Saturno Saturnita and Tung Tung Tung Sahur will have a battle in the Base-$$$b$$$ Game.

The Base-$$$b$$$ Game is played with a collection of piles of stones and an integer $$$b$$$ chosen before the game starts. The two players of the game take turns. On each turn, a player selects a pile of stones and adds a positive number of stones such that the following two conditions are satisfied:

  1. Let $$$a$$$ be the current size of the pile and $$$x$$$ the stones added. The number of digits of $$$x$$$ in base $$$b$$$ doesn't exceed the number of digits of $$$a$$$ in base $$$b$$$. For example, $$$11$$$ has $$$2$$$ digits in base $$$10$$$, $$$9$$$ has $$$4$$$ digits in base $$$2$$$, and $$$0$$$ has $$$1$$$ digit in any base.
  2. The sum $$$a+x$$$ doesn't produce any carry when the sum is performed with the basic addition method in base $$$b$$$.

For example, if $$$b=10$$$, a player can't add $$$28$$$ stones to a pile of size $$$57$$$ since the sum $$$57+28$$$ produces a carry from the units to the tens when performing the sum in base $$$10$$$, as shown in the image below. On the other hand, if $$$b=100$$$, a player can add $$$28$$$ stones to a pile of size $$$57$$$.

The player who can't make a move loses the game. If the game continues for more than $$$2025!^{2025!}$$$ turns, it is declared a tie.

La Vaca Saturno Saturnita will take the first turn. Tung Tung Tung Sahur considered that this was unfair, so he was allowed to choose the sizes of the piles. Sahur can choose any subset (possibly empty) of $$$\{l, l+1, l+2, \dots, r\}$$$ as the sizes of the piles. Note that Sahur can't take multiple piles of the same size.

Tung Tung Tung Sahur is not good at strategy games, so he asks for your help to count the number of ways to choose the sizes of the piles such that he (the second player) has a winning strategy if both of them play optimally. Since the answer can be huge, find it modulo $$$998244353$$$. The order of sizes does not matter, only the chosen subset.

Input

The first line contains three integers $$$b$$$, $$$l$$$ and $$$r$$$ ($$$2 \leq b \leq 100$$$ and $$$0 \leq l \leq r \lt 10^{100}$$$).

Output

Print the anwser modulo $$$998244353$$$.

Examples
Input
10 348 348
Output
1
Input
2 12345678901234567890 98765432109876543210
Output
520579205