409632: GYM103648 I Adeleke's Bird Flocks

Adeleke realizes that the bird flock that she has been watching has a very particular pattern (see a picture of said flock below).

Specifically, she believes that the number of birds in the flock will only be positive integers whose decimal representations contain only the digits $$$3$$$ and $$$8$$$ (so numbers like $$$33$$$, $$$888$$$, and $$$383$$$ are valid but $$$358$$$ is not). Adeleke, being a statistician, wants to compute the following property:

If she chooses a number $$$a$$$ randomly from the interval $$$[a_1, a_2]$$$ and another number $$$b$$$ randomly from the interval $$$[b_1, b_2]$$$. (Each number in $$$[a_1, a_2]$$$ and $$$[b_1, b_2]$$$ - including endpoints of the intervals - is equally likely to be chosen as $$$a$$$ and $$$b$$$ respectively).

She then wants to know what the probability that the interval $$$[\text{min}(a,b), \text{max}(a,b)]$$$ contains exactly $$$k$$$ possible bird flock sizes. Since the probability will be of the form $$$\frac{p}{q}$$$ where both $$$p$$$ and $$$q$$$ are integers, print the integer $$$p \cdot q^{-1}$$$ modulo $$$10^9 + 7$$$.

The input will be a single line containing 5 integers: $$$a_1$$$, $$$a_2$$$, $$$b_1$$$, $$$b_2$$$, and $$$k$$$ separated by a space where $$$1 \leq a_1 \leq a_2 \leq 10^9$$$, $$$1 \leq b_1 \leq b_2 \leq 10^9$$$, and $$$1 \leq k \leq 1000$$$.

Print $$$p \cdot q^{-1}$$$ modulo $$$10^9 + 7$$$ where $$$\frac{p}{q}$$$ represents the probability that the interval contains exactly $$$k$$$ numbers that are possible bird flock sizes.

1 10 1 10 2

260000002

5 6 8 10 1

1