Problem O
Deild Goðsagnanna

Meðlimir Keppnisforritunarfélags Íslands spila Deild Goðsagnanna frekar mikið. Í Deild Goðsagnanna eru tvö lið, bláa liðið og rauða liðið, og samanstendur hvort þeirra af fimm leikmönnum. Hver leikmaður fær að velja eina goðsögn til að spila í leiknum áður en leikurinn hefst og engir tveir leikmenn geta valið sömu goðsögnina.

Þessar goðsagnir hafa veikleika og styrkleika og því er mikilvægt að velja réttu goðsögnina sem passa með goðsögnum liðsfélaga og gegn goðsögnum andstæðinga. Því getur val goðsagnanna skipt miklu máli. Til að koma í veg fyrir að andstæðingar velji sérstakar goðsagnir má hvort liðið banna val á nokkrum goðsögnum. Það verður til þess að hvorugt liðið má velja bönnuðu goðsagnirnar.

Ferlið fyrir hvern leik fer fram í eftirfarandi skrefum:

1. Bláa liðið bannar eina goðsögn.

2. Rauða liðið bannar eina goðsögn.

3. Bláa liðið bannar eina goðsögn.

4. Rauða liðið bannar eina goðsögn.

5. Bláa liðið bannar eina goðsögn.

6. Rauða liðið bannar eina goðsögn.

7. Bláa liðið velur eina goðsögn.

8. Rauða liðið velur tvær goðsagnir í röð.

9. Bláa liðið velur tvær goðsagnir í röð.

10. Rauða liðið velur eina goðsögn.

11. Rauða liðið bannar eina goðsögn.

12. Bláa liðið bannar eina goðsögn.

13. Rauða liðið bannar eina goðsögn.

14. Bláa liðið bannar eina goðsögn.

15. Rauða liðið velur eina goðsögn.

16. Bláa liðið velur tvær goðsagnir í röð.

17. Rauða liðið velur eina goðsögn.

Upprunalega voru bara $20$ goðsagnir til að velja um, ¹ en framleiðendur leiksins eru alltaf að bæta við nýjum goðsögnum. Við segjum að tvö ferli séu mismunandi ef einhver skref eru mismunandi. Núna er hægt að velja um $n$ goðsagnir, á hve marga mismunandi vegu er hægt velja goðsagnir í liðin?

Athugið að það skiptir einungis máli í hvaða skrefi hver goðsögn er valin eða bönnuð.

Hér að neðan má sjá myndir sem tákna þrjú ferli þar sem lið voru valin. Bláa liðið er vinstra megin og rauða liðið er hægra megin. Bannaðar goðsagnir eru í röð frá vinstri til hægri. Valdar goðsagnir eru í röð frá toppi til botns.

Figure 1: Dæmi um ferli þar sem goðsagnir voru bannaðar og valdar.

Í ferlinu að ofan gerist eftirfarandi:

1. Bláa liðið bannar: Gosi.

2. Rauða liðið bannar: Gnýr.

3. Bláa liðið bannar: Örvar.

4. Rauða liðið bannar: Bergur.

5. Bláa liðið bannar: Alda.

6. Rauða liðið bannar: Ólafur.

7. Bláa liðið velur: Krukkutrukkur, hinn fjórði.

8. Rauða liðið velur: Ættingi.

9. Rauða liðið velur: Ljóska.

10. Bláa liðið velur: Vörumerki.

11. Bláa liðið velur: Þrándheim.

12. Rauða liðið velur: Hrútokkur.

13. Rauða liðið bannar: Kippur.

14. Bláa liðið bannar: Spjaldimar.

15. Rauða liðið bannar: Móbergur.

16. Bláa liðið bannar: Valdimar.

17. Rauða liðið velur: Strumpur

18. Bláa liðið velur: Draven.

19. Bláa liðið velur: Mengi.

20. Rauða liðið velur: Þrumuþjarki.

Figure 2: Þetta ferli er jafngilt fyrsta ferlinu.

Í ferlinu að ofan gerist það sama og í ferlinu á undan, nema bláa liðið velur Þrándheim á undan Vörumerki. Þetta eru samt sem áður jafngild ferli þar sem þessi tvö völ eiga sér stað í sama skrefi.

Figure 3: Þetta ferli er frábrugðið hinum tveimur ferlunum.

Í ferlinu að ofan gerist það sama og í fyrsta ferlinu, nema rauða liðið velur Hrútokkur á undan Ljósku. Þessi völ eiga sér stað í mismunandi skrefum og því er þetta ferli frábrugðið fyrri tveimur ferlunum.

Inntak

Inntak er ein lína með einni heiltölu $n$, fjöldi mismunandi goðsagna sem má velja um í leiknum.

Úttak

Segjum að fjöldi leiða til að velja í liðin sé heiltalan $k$. Athugaðu að $k$ getur verið mjög stór tala. Því skaltu skrifa út eina línu með einni heiltölu, afganginn við að deila $k$ með $1\, 000\, 000\, 007$.

Stigagjöf

21

759105918

166

985420928