Fişierul intrare/ieşire:algebra2.in, algebra2.outSursăFMI No Stress 5
AutorDaniel Constantin Anghel, Murtaza AlexandruAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.05 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/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 ≤ 1018

Exemplu

algebra2.inalgebra2.out
2
8

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content