== 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. Ş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.
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^18^$
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") ==
