Laiko ribojimas: 2s

Atminties ribojimas: 256MB

Duomenų failas: trejetai.in

Rezultatų failas: trejetai.out

Jei norite pateikti savo sprendimą - prisijunkite.

Piktieji trejetai

Nagrinėsime sveikųjų skaičių trejetus (a,b,c), kur 0\\leqa,b,c<N. Sakysime, kad trejetas yra piktas moduliu N, jeigu kuris nors iš skaičių a, b ir c yra lygus kitų dviejų skaičių sumai moduliu N.

Pavyzdžiui, trejetas (5, 4, 3) yra piktas moduliu 6, kadangi 3 = (5 + 4) mod 6.

Raskite, kiek yra piktųjų trejetų moduliu N.

Pradiniai duomenys

Vienintelėje įvesties eilutėje yra sveikasis skaičius N (1\\leqN\\leq1~000~000~000).

Rezultatai

Vienoje eilutėje išveskite sveikąjį skaičių – kiek yra piktų trejetų moduliu N.

Pavyzdys

Duomenys Rezultatai 
1
 
1
 
2
 
4

Paaiškinimas

Pirmame pavyzdyje piktas tėra vienintelis trejetas (0, 0, 0), kadangi 0 = (0 + 0) mod 1.

Antrame pavyzdyje yra 4 pikti trejetai: (0, 0, 0), (0, 1, 1), (1, 0, 1) ir (1, 1, 0).