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

Cerința

Să se determine numărul T al tuplelor formate din K numere naturale (X1, X2, X3, …, XK) cu proprietățile:

• 1 ≤ X1 ≤ X2 ≤ X3 ≤ ... ≤ XK ≤ N
• cel mai mare divizor comun al numerelor X1, X2, …, XK 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 restul împărțirii numărului T la 3000017.

Restricții și precizări

• 2 ≤ K ≤ 10.000.000.
• 1 ≤ N ≤ 10.000.000.
• Pentru teste în valoare de 32 puncte, N ≤ 1000
• Pentru 11 puncte, K = 2
• Pentru 44 de puncte, 3 ≤ K ≤ 1000
• Pentru 30 de puncte, 1001 ≤ K ≤ 1.000.000
• Pentru 15 puncte, 1.000.001 ≤ K ≤ 10.000.000
• Pentru 8 puncte, 10.000.000 ≤ K + N ≤ 20.000.000

Exemplul 1:

tupleco.in

2 6

tupleco.out

12

Explicație

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

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

K = 2022 și N = 2023. Restul împărțirii numărului T la 3000017 este 981889.