Kryształy

Limit pamięci: 32 MB

Bajtocy opracował proces tworzenia kryształów złożonych z określonej liczby atomów różnych pierwiastków. Po latach eksperymentów udało mu się znaleźć formułę, która opisuje, dla jakiej liczby atomów poszczególnych pierwiastków można wytworzyć kryształ składający się z tych atomów. Ciekawi go jak wiele różnych kryształów może otrzymać.

Niech i oznaczają nieujemne liczby całkowite. Przez oznaczmy wynik wykonania operacji xor na odpowiadających sobie bitach liczb i . Wyniki działania operacji xor na bitach to: , .

Na przykład, .

Bajtocy zna różnych pierwiastków, ponumerowanych od 1 do . Dla każdego pierwiastka istnieje górne ograniczenie na liczbę atomów tego pierwiastka, jaka może być użyta do stworzenia kryształu. Utworzenie kryształu, który składa się z atomów -tego pierwiastka (dla ) jest możliwe tylko, gdy:

• , dla ,
• , oraz
• .

Zadanie

Napisz program, który:

• Wczyta ze standardowego wejścia liczbę pierwiastków oraz ograniczenia na liczbę atomów danego pierwiastka w krysztale.
• Wyliczy liczbę różnych kryształów jakie można otrzymać.
• Wypisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz standardowego wejścia zawiera liczbę pierwiastków , . W drugim i ostatnim wierszu znajduje się liczb pooddzielanych pojedynczymi odstępami, .

Wyjście

Twój program powinien wypisać na standardowe wyjście jedną liczbę - liczbę kryształów, które można otrzymać. Możesz założyć, że liczba ta jest mniejsza od .

Przykład

Dla danych wejściowych:

3
2 1 3

poprawną odpowiedzią jest:

5

Możliwe ilości atomów poszczególnych pierwiastków to: .

Autor zadania: Jakub Pawlewicz.