Problem C
Gagnageymsla
The IT department at The University of Iceland has to store
an inordinate amount of data for students and employees. Much
of this data is stored automatically, statistics on the usage
of computer services, load on servers and much more. Every year
the databases accrue more and more data so to prevent running
out of storage space there has to be a yearly cleanup. But now
some planning is being done and estimates have to be found for
how much storage space is needed to cover future demand. This
is to be your task.
We know that over the next years the department will have to
store $N$ gigabytes of
data in total. Every year the department will store at least
$1$ gigabyte and at most
$M$ gigabytes. We will
assume that all ways of storing $N$ gigabytes over some number of
years that follow these constraints are equally likely to
occur. For example for $N =
4$ there are $8$
options, for example the department could store $1$ gigabyte a year for four years or
$3$ the first year and
$1$ on the second. At the
end of every year when the cleanup occurs most of the data will
be deleted, but not all of it. More specifically if there are
$x$ gigabytes stored at
the end of the year exactly $\sqrt{x}$ gigabytes will remain after
the cleanup. Note that due to advances in fancy quantum
computing the database is perfectly capable of storing a
non-integer number of bits.
Just before you were about to get cracking you got some extra info from a professor. He said the estimates could be made more accurate since he knew for a fact that the number of gigabytes stored at the end would be an integer, after taking the cleanup of the last year into account. This should help considerably since it eliminates quite a few possibilities. When asked how he could know this, he simply responded “nanomachines” and vanished. Given all of this information, what is the expected number of gigabytes stored in the databases at the end?
Example
Let’s say $N = 14$. Then one way to end up with an integer number of gigabytes would be storing $1, 8, 1, 2$ and $2$ gigabytes over the course of five years, in that order. Then the number of gigabytes left after each yearly cleanup would be $1, 3, 2, 2$ and $2$, in that order. Another equally likely outcome would be registering $2, 2, 1$ and $9$ gigabytes over the course of $4$ years, in that order. In both of these examples the final number of stored gigabytes is $2$.
Input
The input contains a single line containing two integers $1 \leq N, M \leq 5000$, the total number of gigabytes stored and the maximum number of gigabytes stored per year.
Output
If the professor’s info is wrong, that is if there is no way to end up with an integer number of gigabytes given the other info, print $-1$. Otherwise print the expected number of gigabytes at the end of the process given the info above. The expectation will always be some integer fraction of the form $p / q$ with $q \neq 0$. Rather than printing this fraction, instead print $pq^{-1} \pmod{10^9+7}$ where $q^{-1}$ is the multiplicative inverse of $q$ modulo $10^9 + 7$.
| Sample Input 1 | Sample Output 1 |
|---|---|
14 8 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
25 6 |
-1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
100 50 |
891168391 |
