1794.
Feeding the Herrings
时间限制 5000 ms
内存限制 128 MB
Zookeper Willy is feeding herrings today. He is feeding them to seals, as they are their preferred
food. There are three separate pools in which the seals live. The ZOO is a modern institution
and it demands their employees to keep track of feeding habits of animals. There is a touchscreen
installed at the seals pools and Willy has to enter the number of herrings which he is going to
deposit into each of the three pools. Unfortunately, the screen is not working properly - in
particular, it is impossible to enter the digit ‘3’.
Willy called the chief marine mammals zookeper and asked for help.
“That is OK,” said the chief, “just distribute the herrings in such a way that the number of
herrings which go into each pool does not contain the digit ‘3’.”
“But there is a lower limit L on the number of herrings which have to be put into each pool,”
reacted Willy, “I might not be able to find a suitable division.”
“You will be able to find a suitable division,” assured him the chief, “considering the numbers
of herrings in the bucket, there should be zillions of possible divisions.”
“Well, exactly how many?” wondered Willy for himself.
You will be given the total number N of herrings which are to be deposited into the seals pools
and the lower limit L on the number of herrings in each of the pools. Find out in how many
ways might these N herrings be placed into the pools in such a way that the number of herrings
in each pool does not contain digit ‘3’ in its decimal representation. In this problem, we do
not distinguish between individual herrings as they are all more or less of the same size and
nutrition value. We do distinguish between the pools, though, because they are populated by
different groups of seals. Also, we suppose that no herring can be divided into pieces.
输入数据
输出数据
For each test case print on a separate line the number of possible divisions of the herrings into
the three given pools. Express the result modulo 12345647.
样例输入
复制
3 1
4 1
7 2
99999 1
0 0 · \n
· \n
· \n
· \n
· \n
样例输出
复制
1 3 0
9521331 · · \n
\n