Tyrannosaurus (/tɪˌrænəˈsɔːrəs, taɪ-/, có nghĩa là thằn lằn bạo chúa, được lấy từ tiếng Hy Lạp “tyrannos” (τύραννος) nghĩa là “bạo chúa”, và “sauros” (σαῦρος) nghĩa là “thằn lằn”), còn được gọi là Khủng long bạo chúa trong văn hóa đại chúng, là một chi khủng long chân thú sống vào cuối kỷ Phấn Trắng. Chi này chỉ gồm một loài duy nhất là Tyrannosaurus rex (thường rút gọn là T - rex). Chúng sinh sống ở nơi ngày nay là phía Tây của Bắc Mỹ, khi đó là một lục địa đảo, tên là Laramidia. Hóa thạch của Tyrannosaurus được tìm thấy trong các thành hệ địa chất có niên đại tầng Maastricht, khoảng 67-65,5 triệu năm về trước, và là một trong những loài khủng long cuối cùng tồn tại trước sự kiện tuyệt chủng Phấn Trắng – Cổ Cận.

Như các loài bạo long chuẩn (Tyrannosauridae) khác, Tyrannosaurus rex là loài ăn thịt đi bằng hai chân, với một hộp sọ lớn và giữ thăng bằng bởi cái đuôi dài, nặng. So với hai chi sau to khỏe, chi trước của Tyrannosaurus thì ngắn nhưng đặc biệt mạnh so với kích thước của nó và có hai ngón có móng vuốt. Mặc dù bị nhiều loài khác vượt qua về kích thước, Tyrannosaurus rex vẫn là bạo long chuẩn lớn nhất và một trong số những động vật ăn thịt lớn nhất mọi thời đại. Mẫu vật hoàn chỉnh nhất dài 12,3 m (40 ft), cao 4 mét (13 ft) tới hông (13 feet) và nặng 6,8 tấn (7,5 tấn Mỹ). Là động vật ăn thịt lớn nhất trong khu vực của nó, Tyrannosaurus rex là một động vật ăn thịt đầu bảng, săn khủng long mỏ vịt, khủng long mặt sừng, giáp long và có thể cả khủng long chân thằn lằn, mặc dù vài nhà khoa học xem loài này ăn xác thối. Việc Tyrannosaurus ăn thịt hay xác thối là một trong những chủ đề gây tranh cãi nhiều nhất trong giới cổ sinh vật học; tuy nhiên, hiện nay hầu hết đều đồng ý rằng Tyrannosaurus rex là loài săn mồi cơ hội, thực hiện cả ăn thịt và xác thối. Nó một trong số động vật trên cạn có lực cắn lớn nhất. Hơn 50 mẫu vật Tyrannosaurus rex đã được phát hiện, một vài có bộ xương gần như hoàn chỉnh. Mô mềm và protein đã xuất hiện trong ít nhất một mẫu vật. Thói quen săn mồi, sinh lý học và tốc độ Tyrannosaurus rex là một vài chủ đề tranh cãi. Việc phân loại cũng bị tranh luận, vài nhà khoa học xem Tarbosaurus bataar từ châu Á là một loài Tyrannosaurus và số khác vẫn cho rằng Tarbosaurus là một chi riêng. Nhiều chi Tyrannosauridae Bắc Mỹ cũng đồng nghĩa với Tyrannosaurus.

Kiếm ăn thời tiền sử không phải là một việc dễ làm. Nhóm nghiên cứu A2K52 PBC phát hiện rằng trong môi trường T-Rex đang ở, một ngày được coi là đẹp nếu mãn ngày số có số lượng chữ số khác nhau của nó phải bé hơn hoặc bằng k. Ví dụ với \(k = 2, 122\) là ngày đẹp do chúng chỉ có 2 số khác nhau là 1, 2. Tương tự như vậy, ngày \(12312312\) là ngày đẹp vỡi \(k = 3\), nhưng không phải là ngày đẹp nếu \(k = 2\).Do khủng long không biết code và nên nhiệm vụ của bạn làm đếm số lượng ngày đẹp cho khủng long đi săn mồi nhé!

Input:

• Ba số nguyên \(l, r, k\) được nhập từ bàn phím \((0 \leq l < r \leq {10}^{1000}, 0 < k < 10)\)

Ouput:

Số lượng số ngày thỏa mãn điều kiện trên, nếu kết quả lớn hơn \(1000000007\) thì chỉ lấy phần dư cho \(1000000007\).

Ví dụ 1:

1 88828928489283928392839193892 3

Kết quả 1:

396600998

Ví dụ 2

101 154 2

Kết quả 2:

18

Giải thích test 2: Các số thỏa mãn là 101, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 121, 122, 131, 133, 141, 144, 151.