In an imaginary country the cities a located by a semicircle around a desert and are connected by one road (not cyclically). There is a research zone in the desert where different diseases are investigated and there are different virus diseases among others. One day two tested buffalo escaped from the desert and headed to the main road. Each of the buffalo was infected by an individual experimental disease. Those viruses were very contagious but not transferable to a carrier of an alternative strain. The government immediately ordered to a department K to analyze a possibility of infection and options of quarantine, taking in consideration that buffalo moved on direction to different cities and already achieved them for sure. The following decision was made. In case of reveal of infection in a city the quarantine in it is announced. If in the neighbor city the same strain disease is revealed, the quarantine is widened to this city too. But just in case it was decided to not unite the quarantine zone of different strain of the virus.
Task. Find quantity of options of viruses localization in a system of N connected cities taking in consideration that viruses can be spread to neighbor cities connected by the main road only and two cities (it is not know which) are already infected by different strains of virus.
Streams. Input stream contains one positive integer N. Output stream contains one positive integer.