Fişierul intrare/ieşire:	algebra2.in, algebra2.out	Sursă	FMI No Stress 5
Autor	Daniel Constantin Anghel, Murtaza Alexandru	Adăugată de	FMI No Stress •fmins123
Timp execuţie pe test	0.025 sec	Limită de memorie	5120 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Algebra2

Pentru că se apropie sesiunea şi mai trebuie să punem mâna să învăţăm şi pe la mate, vă propunem să considerăm o mulţime A cu N elemente şi să definim pe ea o operaţie binară, internă, comutativă *. Operaţia este binară întrucât se realizează între doi operanzi (oricare 2 elemente x,y din A). Operaţia este internă intrucât rezultatul x * y aparţine lui A. Şi nu în ultimul rând, operaţia este comutativă întrucât x * y este mereu egal cu y * x.

Câte operaţii binare, interne şi comutative se pot defini pe A ? Două operaţii + şi * se consideră a fi diferite dacă există două elemente din A: x şi y pentru care x * y este diferit de x + y.

Date de intrare

Fişierul de intrare algebra2.in conţine un singur număr: cardinalul (numărul de elemente) al mulţimii A.

Date de ieşire

În fişierul de ieşire algebra2.out se va afişa un singur număr, răspunsul la problemă. Cum acest număr poate fi destul de mare, se cere doar restul împărţirii lui la 1000000009.

Restricţii

• 1 ≤ N ≤ 10¹⁸

Exemplu

Explicaţie

Fie 1 şi 2 elementele mulţimii A. Există 8 operaţii interne ce pot fi definite:

1. 1 + 1 = 1 , 2 + 2 = 1 , 1 + 2 = 1
2. 1 @ 1 = 1 , 2 @ 2 = 1 , 1 @ 2 = 2
3. 1 # 1 = 1 , 2 # 2 = 2 , 1 # 2 = 1
4. 1 $ 1 = 2 , 2 $ 2 = 1 , 1 $ 2 = 1
5. 1 - 1 = 1 , 2 - 2 = 2 , 1 - 2 = 2
6. 1 ~ 1 = 2 , 2 ~ 2 = 2 , 1 ~ 2 = 1
7. 1 & 1 = 2 , 2 & 2 = 1 , 1 & 2 = 2
8. 1 * 1 = 2 , 2 * 2 = 2 , 1 * 2 = 2

Cum se trimit solutii?