Hosoyev indeks

Osnovne informacije

Omejitve
  • Čas: 1 s
  • Spomin: 128 MB
Avtor:
  • Tomaž Hočevar
  • UPM 2019

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Hosoyev indeks grafa je definiran kot število vseh možnih prirejanj (angl. matchings) v njem. Prirejanje v grafu je taka podmnožica povezav, da nobeni dve povezavi nimata skupnega krajišča. Npr. graf P_4 (pot na štirih vozliščih) ima 5 prirejanj: 1 prazno množico povezav, 3 prirejanja s po eno povezavo in 1 prirejanje z 2 povezavama. Gre za pomembno grafovsko invarianto s področja kemijske teorije grafov.

Helicen je molekula, ki je sestavljena iz spiralne verige benzenskih obročev. Strukturo molekule lahko modeliramo z grafom, ki je sestavljen iz zaporedja ciklov C_6 (šestkotnikov), ki so zaporedoma zlepljeni v obliko spirale, kot je prikazano na spodnjih slikah (heliceni velikosti 4, 6 in 14). Pri modeliranju ignoriramo vodikove atome in tipe vezi. Velikost helicena merimo s številom benzenskih obročev, ki ga sestavljajo. Tako je helicen velikosti 1 enak grafu C_6.

Heliceni

Bolj formalno lahko helicen velikosti N definiramo na sledeč način: Vzemimo N kopij grafa C_6, kjer v_i^k označuje i-to vozlišče v k-ti kopiji (1 \leq i \leq 6 in 1 \leq k \leq N). Če identificiramo povezavi v_5^{k}v_6^{k} in v_2^{k+1}v_1^{k+1} za vse k = 1, 2, \ldots, N - 1, dobimo helicen velikosti N.

Napišite program, ki bo izračunal Hosoyev indeks helicena podane velikosti. Ker je rezultat lahko zelo velik, določite samo njegov ostanek pri deljenju z 1\,000\,000\,007.

Vhodni podatki

V prvi vrstici se nahaja celo število T, tj. število testnih primerov. Vsak testni primer je podan v svoji vrstici z velikostjo helicena N.

Omejitve vhodnih podatkov

  • 1 \leq T \leq 10
  • 1 \leq N \leq 10^{15}

Izhodni podatki

Za vsak testni primer izpišite iskan rezultat v svoji vrstici.

Primeri

Vhod

3
1
2
5

Izhod

18
148
85169
Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task