submultprime

Se dă un număr natural $N$. Vom nota cu $P$ mulțimea numerelor prime mai mici sau egale cu $N$. Dorim să determinăm cea mai mare sumă a unei submulțimi a lui $P$, cu $[card(P)/2]$ elemente și numărul de submulțimi nevide ale lui $P$, modulo $7919$.

Cerință

Cunoscând $N$ se cere:

1. cea mai mare sumă a unei submulțimi a lui $P$ cu $[card(P)/2]$ elemente;
2. numărul de submulțimi nevide ale lui $P$, modulo $7919$.

Date de intrare

Pe prima linie și a doua linie a fișierului de intrare submultprime.in se găsesc două numere naturale, $C$ și $N$ reprezentând numărul cerinței ce se va rezolva ($1$ sau $2$), respectiv numărul din enunț.

Date de ieșire

Pe prima linie a fișierului de ieșire submultprime.out se va găsi un singur număr natural corespunzător rezolvării cernței $C$ din fișierul de intrare.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$;
• Pentru o multime $M$, $card(M)$ reprezintă numărul de elemente al lui $M$.
• Pentru rezolvarea corectă a cerinței $1$ se vor acorda $20$ de puncte.
• Pentru rezolvarea corectă a cerinței $2$ se vor acorda $80$ de puncte.

Exemplul 1

submultprime.in

1
10

submultprime.out

12

Explicație

$C = 1$. Obținem că $P = \{2, 3, 5, 7\}$, $card(P) = 4$. Suma cea mai mare pentru o submulțime cu două elemente este $5 + 7 = 12$.

Exemplul 2

submultprime.in

2
10

submultprime.out

15

Explicație

$C = 2$. Numărul de submulțimi nevile ale lui $P = \{2, 3, 5, 7\}$ este $15$.