== include(page="template/taskheader" task_id="algebra2") ==

Poveste şi cerinţă...

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. 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.

h2. Date de intrare

Fişierul de intrare $algebra2.in$ ...

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

h2. Date de ieşire

În fişierul de ieşire $algebra2.out$ ...

Î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.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 10^9$

h2. Exemplu
table(example). |_. algebra2.in |_. algebra2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2
| 8

|
h3. 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

== include(page="template/taskfooter" task_id="algebra2") ==