Doti trīs skaitļi L, R, un K. Nosakiet cik ir tādu skaitļu intervālā [L; R], kuriem izpildās šāda īpašība:

• Tas ir vismaz K ciparus garš.
• Neviens cipars tā pierakstā nav 0.
• Katri K secīgi cipari tajā veido pirmskaitli.

Piemēram, skaitlis 791 ir 2-pirmskaitlis, jo skaitļi 79 un 91 ir pirmskaitļi. Noslēpumainu iemeslu dēļ prasītais skaitlis ir jāizvada pēc moduļa 10^9 + 7.

Ievaddatu pirmajā rindā doti skaitļi L, R, un K.

1 <= L <= R < 10^700

1 <= K <= 5

Izvaddatu pirmajā rindā jāizvada prasītais skaitļu skaits pēc moduļa 10^9 + 7.

Testu grupas:

• 10 punkti: 1 <= L <= R <= 10^5
• 20 punkti: K = 1
• 70 punkti: Bez papildus ierobežojumiem

Skaitlis 1 nav pirmskaitlis.

1. piemērā visi derīgie skaitļi ir: 2, 3, 5, 7, 22, 23, 25, 27, 32, 33, 35, 37, 52, 53, 55, 57, 72, 73, 75, 77