На сегодняшней лекции Профессор Р. рассказал студентам о бинарных деревьях. Бинарное дерево или двоичное дерево – это дерево, в котором у каждого из его узлов не более двух дочерних узлов. При этом каждый дочерний узел тоже представляет собой бинарное дерево. Пример бинарного дерева показан на рисунке ниже.
Также профессор ввёл понятие высоты дерева. Высота двоичного дерева – высота его корневого узла. Дерево из примера имеет высоту 6. Вершины, находящиеся на одной высоте, образуют уровни с первого (корень) по шестой (вершины с номерами $$$3$$$ и $$$5$$$)
На дом студентам была дана следующая задача.
Имеется бинарное дерево, обладающее следующими свойствами:
- Его высота равна $$$n$$$;
- На уровнях $$$1 \dots n - 2$$$ у каждой вершины $$$2$$$ сына.
Требуется вычислить, каким минимальным и максимальным может быть количество вершин в этом дереве.
Помогите студентам – напишите программу, которая сможет найти требуемые профессором Р. значения.
В единственной строке содержится число $$$n$$$ $$$(1 \le n \le 10^{18})$$$ – высота бинарного дерева.
В единственной строке выведите два числа разделенных пробелом – минимальное и максимальное число вершин в искомом бинарном дереве. Так как это число может быть очень большим, требуется вывести остатки от деления количеств вершин на число $$$10^9 + 7$$$.
1
1 1
1000000
617521033 235042058
