406786: GYM102556 B Riana and the Blind Date

Last valentines, Riana went on a blind date with Zanoki-kun, a famous shoujo manga mangaka, but after a series of misunderstandings, she accidentally became one of his manga assistants.

In his new manga, Biidoru wa Meido-sama! (Class Beadle is Maid!), he adopts a new system of expressing dates on a calendar. In this system, Zanoki-kun takes the numerical value of the month (January = $$$1$$$, February = $$$2$$$, March = $$$6$$$, ... , November = $$$11$$$, December = $$$12$$$), and appends the day to it. Thus, representing each date as a single integer.

For example:

January $$$1$$$ becomes $$$11$$$.

February $$$23$$$ becomes $$$223$$$.

November $$$5$$$ becomes $$$115$$$.

December $$$24$$$ becomes $$$1224$$$.

It just so happens that it takes Zanoki-kun $$$1$$$ pencil to draw the integer '$$$1$$$', $$$2$$$ pencils to draw the integer '$$$2$$$', and so on. Generally, it takes Zanoki-kun $$$n$$$ pencils to draw the integer '$$$n$$$'.

In chapter $$$1$$$ of Biidoru wa Meido-sama!, Zanoki-kun decides to draw all the dates from year $$$A$$$ to year $$$B$$$ inclusive. Zanoki-kun wants to prepare all the pencils he needs before he starts drawing, but he doesn't want to waste any more money than he has to, so he commissions his manga assistants, including Riana, to compute the least number of pencils he needs to draw all the dates from year $$$A$$$ to year $$$B$$$ inclusive. Note that the date does not include the year.

More formally, let $$$S$$$ be the least number of pencils Zanoki-kun needs in order to draw all the dates from year $$$A$$$ and year $$$B$$$ inclusive. Find $$$S$$$ given $$$A$$$ and $$$B$$$.

Note that three criteria must be taken into account to identify leap years:

• The year can be evenly divided by $$$4$$$;
• If the year can be evenly divided by $$$100$$$, it is NOT a leap year, unless;
• The year is also evenly divisible by $$$400$$$. Then it is a leap year.

Two spaced integers $$$A$$$ and $$$B$$$. The first integer, $$$A$$$, is the year that Zanoki-kun chooses to begin drawing at. The second integer, $$$B$$$, is the year that Zanoki-kun chooses to end drawing at.

It is guaranteed that $$$A$$$ and $$$B$$$ ranges from $$$0$$$ to $$$10^{18}$$$ inclusive. ($$$0 \leq A \leq B \leq 10^{18}$$$)

Output the least number of pencils Zanoki-kun needs in order to draw all the dates from year $$$A$$$ and year $$$B$$$ inclusive. Since the answer can get quite large, output only the positive remainder when $$$S$$$ is divided by $$$104206969$$$, Zanoki-kun's favorite a prime number.

1 3

542274

$$$11 + 12 + \ldots + 21 + 22 + \ldots + 31 + 32 + \ldots + 41 + 42 + \ldots + 51 + 52 + \dots + 61 + 62 + \ldots$$$ $$$+ 71 + 72 + \ldots + 81 + 82 + \ldots + 91 + 92 + \ldots + 101 + 102 + \ldots + 111 + 112 + \ldots$$$ $$$+ 121 + 122 + \ldots + 11 + 12 + \ldots + 21 + 22 + \ldots + 31 + 32 + \ldots + 41 + 42 + \ldots + 51 + 52 + \ldots$$$ $$$+ 61 + 62 + \ldots + 71 + 72 + \ldots + 81 + 82 + \ldots + 91 + 92 + \ldots + 101 + 102 + \ldots + 111 + 112 + \ldots$$$ $$$+ 121 + 122 + \ldots + 11 + 12 + \ldots + 21 + 22 + \ldots + 31 + 32 + \dots + 41 + 42 + \ldots + 51 + 52 + \ldots$$$ $$$+ 61 + 62 + \ldots + 71 + 72 + \ldots + 81 + 82 + \ldots + 91 + 92 + \ldots + 101 + 102 + \ldots$$$ $$$+ 111 + 112 + \ldots + 121 + 122 + \ldots + 1230 + 1231 = 542274$$$