tupleco

Se consideră două numere naturale $K$ și $N$.

Cerință

Să se determine numărul $T$ al tuplelor formate din $K$ numere naturale $(X_1, X_2, X_3, \dots, X_K)$ cu proprietățile:

• $1 \leq X_1 \leq X_2 \leq X_3 \leq \dots \leq X_K \leq N$
• cel mai mare divizor comun al numerelor $X_1, X_2, X_3, \dots , X_K$ este $1$.

Date de intrare

Fișierul de intrare tupleco.in conține pe prima linie numerele naturale $K$ și $N$, separate printr-un spațiu.

Date de ieșire

Fișierul de ieșire tupleco.out va conține pe prima linie restul împărțirii numărului $T$ la $3 \ 000 \ 017$.

Restricții și precizări

• $2 \leq K \leq 10 \ 000 \ 000$.
• $1 \leq N \leq 10 \ 000 \ 000$.
• Pentru teste în valoare de $32$ puncte, $N \leq 1 \ 000$

Exemplul 1

tupleco.in

2 6

tupleco.out

12

Explicație

Pentru primul exemplu avem $K = 2$ și $N = 6$.

Există 12 perechi de numere naturale ce respectă condițiile din enunț: $(1,1)$, $(1,2)$, $(1,3)$, $(1,4)$, $(1,5)$, $(1,6)$, $(2,3)$, $(2,5)$, $(3,4)$, $(3,5)$, $(4,5)$ și $(5,6)$.

Exemplul 2

tupleco.in

4 3

tupleco.out

13

Explicație

Pentru al doilea exemplu avem $K = 4$ și $N = 3$.

Există $13$ tuple formate din câte $4$ numere naturale ce respectă condițiile din enunț: $(1,1,1,1)$, $(1,1,1,2)$, $(1,1,1,3)$, $(1,1,2,2)$, $(1,1,2,3)$, $(1,1,3,3)$, $(1,2,2,2)$, $(1,2,2,3)$, $(1,2,3,3)$, $(1,3,3,3)$, $(2,2,2,3)$, $(2,2,3,3)$ și $(2,3,3,3)$.

Exemplul 3

tupleco.in

2022 2023

tupleco.out

981889

Explicație

Pentru al treilea exemplu avem $K = 2022$ și $N = 2023$.

Restul împărțirii numărului $T$ la $3 \ 000 \ 017$ este $981 \ 889$.