Nosaukums
K pirmskaitļi (k_pirmskaitli)
Laika limits
2.00s
Atmiņas limits
128.0 MB
Grūtība
60%

Definīcija

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 raksturojums

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

1 <= L <= R < 10^700

1 <= K <= 5


Izvaddatu raksturojums

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


Piezīmes

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


Paraugdati

Stdin
1 100000000000000000 5
Stdout
138978

Stdin
1 100 1
Stdout
20

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.