Pedaso overflow P43384


Statement
 

pdf   zip

html

Emocionat per la medalla guanyada al SWERC, l’Eric vol regalar un eslip enorme a un company de la FME. Per fer la comanda per internet l’Eric n’ha de precisar la talla, però la pàgina web no funciona bé. Per començar, només existeix un natural n que el web reconegui com a número; les altres combinacions de xifres fan que la pàgina es pengi. Per sort, la pàgina també permet l’ús dels operadors suma, multiplicació i exponenciació, i es poden usar tants parèntesis com es vulgui.

L’Eric vol comprar l’eslip més gran possible sota aquestes condicions, però la pàgina web només permet usar el nombre n com a molt d vegades. Podeu ajudar-lo a maximitzar la talla? Per les condicions del problema (i el futur propietari de l’eslip) el nombre resultant pot fer overflow, així que cal fer els càlculs mòdul un natural m.

Entrada

L’entrada consisteix en diversos casos, cadascun amb n, d i m. Podeu suposar 10 ≤ n ≤ 106, 1000 ≤ d ≤ 106, i 2 ≤ m ≤ 106.

Sortida

Per a cada cas, escriviu la talla màxima mòdul m.

Public test cases

  • Input

    10 1000 1000000
11 1000 1000000
10 1000 999999

    Output

    0
666611
10000
    • Information
    Author
    Ivan Geffner
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++