
ZOJ Problem Set  4137
Define the "digit product" $f(x)$ of a positive integer $x$ as the product of all its digits. For example, $f(1234) = 1 \times 2 \times 3 \times 4 = 24$, and $f(100) = 1 \times 0 \times 0 = 0$. Given two integers $l$ and $r$, please calculate the following value: $$(\prod_{i=l}^r f(i)) \mod (10^9+7)$$ In case that you don't know what $\prod$ represents, the above expression is the same as $$(f(l) \times f(l+1) \times \dots \times f(r)) \mod (10^9+7)$$ InputThere are multiple test cases. The first line of the input contains an integer $T$ (about $10^5$), indicating the number of test cases. For each test case: The first and only line contains two integers $l$ and $r$ ($1 \le l \le r \le 10^9$), indicating the given two integers. The integers are given without leading zeros. OutputFor each test case output one line containing one integer indicating the answer. Sample Input2 1 9 97 99 Sample Output362880 367416 HintFor the first sample test case, the answer is $9! \mod (10^9+7) = 362880$. For the second sample test case, the answer is $(f(97) \times f(98) \times f(99)) \mod (10^9+7) = (9 \times 7 \times 9 \times 8 \times 9 \times 9) \mod (10^9+7) = 367416$. Author: WENG, Caizhi Source: The 2019 ICPC China Shaanxi Provincial Programming Contest 