Razvijaš novu, eksperimentalnu arhitekturu za Veliki Jezični Model (LLM). Njegov latentni prostor može se zamisliti kao beskonačna dvodimenzionalna ravnina.

Na početku, svi tokeni (točke) na toj ravnini su inicijalno neaktivni (bijele točke), osim tri fiksna čvora za jezgrenu pažnju (crvene točke) i dva početna kontekstualna čvora (plave točke).

Proces učenja modela odvija se iterativno kroz dane. Svakog dana događa se sljedeće:

1. Model konstruira neuronske veze (linije). Gradi se svaka moguća linija koja prolazi kroz jednu crvenu točku i jednu plavu točku.
2. Zatim, svaka neaktivna (bijela) točka u kojoj se presijeku dvije različite takve linije, postaje aktivirana (pretvara se u plavu točku).

Ove nove plave točke postaju dio dostupnog konteksta i već idućeg dana mogu sudjelovati u povlačenju novih linija s crvenim točkama.

Neka je f(D) maksimalan mogući broj plavih točaka nakon D dana treninga. S obzirom na to da arhitektura raste eksponencijalno, izračunavanje broja aktiviranih čvorova za napredne faze treninga postaje izuzetno zahtjevno.

Tvoj zadatak je izračunati f(D). Zbog ogromne veličine rezultata, rješenje je potrebno ispisati modulo 1000000007.

Ulazni podatci

Ulaz se sastoji od jedne linije koja sadrži jedan cijeli broj \(D\) (\(1 \leq D \leq 10^5\)) – dan treninga modela.

Izlazni podatci

Ispiši jedan cijeli broj – maksimalan mogući broj plavih točaka f(D) modulo 1000000007.

Ulaz primjera 1

16

Izlaz primjera 1

848947596

Ulaz primjera 2

1

Izlaz primjera 2

8