Известный итальянский ресторан разрешает гостям входить только в том случае, если они присутствуют парами и сумма богатства людей пары равна степени числа . Группа людей хочет поесть в ресторане. С математической точки зрения, если имеются два человека с состоянием и , то они образуют правильную пару если для некоторого натурального числа . Выясните, скольким возможным парам будет разрешен вход.
Первая строка содержит количество гостей . Вторая строка содержит индивидуальное богатство человек.
Выведите количество допустимых пар. Известно, что:
Один человек может быть в нескольких допустимых парах.
Пара лиц и аналогична паре лиц и .