Waga czwórkowa

Limit pamięci: 32 MB

Smok Bajtazar zamierza zorganizować ucztę, na którą chce zaprosić wielu gości. Dla uświetnienia uczty, Bajtazar chce każdemu z gości podarować pewną ilość złota. Przy tym, każdy z gości powinien dostać tyle samo złota, aby nikt nie czuł się pokrzywdzony.

Smok będzie odważał złoto dla kolejnych gości wagą szalkową. Ma on do dyspozycji odważniki, których wagi w gramach są potęgami czwórki. Przy tym odważników każdego rodzaju ma dowolnie wiele. Bajtazar będzie zawsze kładł złoto na lewej szalce wagi, a odważniki na prawej lub na obu szalkach. Bajtazar przy każdym ważeniu chce użyć najmniejszej możliwej liczby odważników. Ponadto, aby gościom się nie nudziło, chce on każdemu z nich odważyć złoto w inny sposób (tzn. używając innych odważników lub inaczej je rozdzielając pomiędzy szalki).

Ponieważ smok nie umie za dobrze liczyć, polecił ci napisanie programu, który obliczy ilu maksymalnie gości może zaprosić, czyli wyznaczy maksymalną liczbę sposobów, na jakie można odważyć gramów złota używając minimalnej liczby odważników. Jeśli dobrze się sprawisz, smok obsypie Cię złotem!

Zadanie

Napisz program który:

  • wczyta ze standardowego wejścia ile złota (w gramach) Bajtazar zamierza dać każdemu z gości,
  • obliczy na ile sposobów można odważyć taką ilość złota za pomocą minimalnej liczby odważników,
  • wypisze resztę z dzielenia wyniku przez na standardowe wyjście.

Wejście

W pierwszym i jedynym wierszu standardowego wejścia zapisania jest jedna liczba całkowita , . Jest to ilość złota (w gramach), jaką Bajtazar chce dać każdemu z gości.

Wyjście

Na standardowe wyjście należy wypisać jedną liczbę całkowitą - resztę z dzielenia przez maksymalnej liczby gości, których Bajtazar może zaprosić (czyli maksymalnej liczby sposobów, na jakie można odważyć gramów złota używając minimalnej możliwej liczby odważników).

Przykład

Dla danych wejściowych:

166

poprawną odpowiedzią jest:

3

Do odważenia 166 gramów potrzeba użyć 7 odważników. Ważenie można wykonać na następujące sposoby:

  1. na lewej szalce złoto, na prawej odważniki 64, 64, 16, 16, 4, 1, 1,
  2. na lewej szalce złoto i odważniki 64, 16, 16, na prawej odważniki 256, 4, 1, 1,
  3. na lewej szalce złoto i odważniki 64, 16, 4, 4, 1, 1, na prawej odważnik 256.

Autorzy zadania: Wojciech Rytter i Andrzej Walat.