Số Có Chữ Số May Mắn

Buổi 35 — Digit DP Dynamic Programming
Points
38
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Các chữ số $4$ và $7$ được gọi là các chữ số may mắn. Một số nguyên dương được gọi là số may mắn nếu biểu diễn thập phân của nó chỉ gồm toàn các chữ số $4$ và $7$.

Cho hai số nguyên dương $L, R$ và số nguyên dương $K$. Hãy đếm số lượng số nguyên $x$ trong đoạn $[L, R]$ sao cho:

  1. Số lượng chữ số may mắn (chữ số $4$ hoặc $7$) xuất hiện trong $x$ là một số may mắn (tức là bằng $4$ hoặc $7$).
  2. $x$ chia hết cho $K$.

In kết quả chia dư cho $10^9 + 7$.

Dữ liệu vào
  • Một dòng chứa ba số nguyên $L, R, K$.
Dữ liệu ra
  • Một số nguyên duy nhất là kết quả bài toán chia dư cho $10^9 + 7$.
Ví dụ
Input Output
1 10000 1 16
1 100000 10 16
Giới hạn
  • $1 \le L \le R \le 10^{18}$
  • $1 \le K \le 100$
Draft saved