fractii2

Numărul 1 poate fi scris în diverse moduri ca sumă de fracții cu numărătorul 1 și numitorul o putere a lui 2. De exemplu:

$\displaystyle 1=\frac{1}{2}+\frac{1}{2}=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{1}{8}=\frac{1}{8}+\frac{1}{4}+\frac{1}{2}+\frac{1}{8}$

Două scrieri nu sunt considerate distincte dacă folosesc aceleași fracții scrise în altă ordine. În exemplul de mai sus ultimele două scrieri nu sunt distincte.

Cerință

Pentru N – număr natural nenul să se determine:
a. O modalitate de scriere a numărului 1 ca sumă de exact N fracții cu numărătorul 1 și numitorul o putere a lui 2.
b. Numărul de scrieri distincte a numărului 1 ca sumă de exact N fracții cu numărătorul 1 și numitorul o putere a lui 2. Deoarece acest număr poate fi foarte mare acest număr trebuie calculat modulo 100003.

Date de intrare

Fişierul de intrare fractii2.in conţine pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2.
Pe a doua linie se găsește un singur număr N natural – reprezentând numărul de fracții.

Date de ieșire

Dacă valoarea lui p este 1, se va rezolva numai punctul a) din cerință. În acest caz, în fişierul de ieşire fractii2.out se vor scrie, pe o singură linie, N numere naturale separate prin câte un spațiu reprezentând cei N exponenți ai lui 2 din scrierea solicitată în prima cerință. Astfel, dacă numerele afișate sunt $m_1,m_2,…,m_N$ atunci există scrierea $1=\frac{1}{2^{m_1}}+\frac{1}{2^{m_2}}+⋯+\frac{1}{2^{m_N}}$ .
Dacă valoarea lui p este 2, se va rezolva numai punctul b) din cerință. În acest caz, în fişierul de ieşire fractii2.out se va scrie un număr natural reprezentând răspunsul la a doua cerință, adică numărul de scrieri distincte a numărului 1 ca sumă de N fracții cu numărătorul 1 și numitorul o putere a lui 2 (modulo 100003).

Restricții

• 2 ≤ N ≤ 2000
• Pentru prima cerință se acordă 20% din punctaj.
• Pentru a doua cerință de acordă 80% din punctaj.
• Rezultatul pentru a doua cerință trebuie afișat modulo 100003

Exemple

fractii2.in

1
4

fractii2.out

2 2 2 2

fractii2.in

2
4

fractii2.out

2

Explicații

Pentru primul test:
p=1
$1=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{1}{8}=\frac{1}{4}+\frac{1}{4}+\frac{1}{4}+\frac{1}{4}$
Răspunsul corespunde celei de-a doua scrieri dar există și alte variante corecte de răspuns. De exemplu, 3 1 2 3 se consideră răspuns corect.
Atenție! Pentru acest test se va afișa doar rezultatul la cerința a).

Pentru al doilea test:
p=2
$1=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{1}{8}=\frac{1}{4}+\frac{1}{4}+\frac{1}{4}+\frac{1}{4}$
Acestea sunt singurele scrieri distincte.
Atenție! Pentru acest test se va afișa doar rezultatul la cerința b).