Задачка по программированию. Можно на любом языке.

Тем временем Рик продолжал вспоминать разные моменты из своего прошлого. Ему пришла в голову задача, которую он встретил несколько лет назад. Дано натуральное число n, и на доске изначально написано n × n. Затем k раз проделывают следующую операцию: вместо каждого вхождения n × n записывается n раз число n. Далее между парами этих чисел ставят скобки, объединяя первое со вторым, третье с четвертым, и так далее. Если число n нечетно, то последнее его вхождение в этой записи не заключается в скобки. Затем внутри этих скобок ставится символ “×”, а между скобками или перед последним числом n — обыкновенное умножение “⋅”.

После k-й итерации данного процесса, все оставшиеся вхождения “×” так же заменяются на “⋅”. Рика интересует, сколько символов умножения будет написано на доске после выполнения всех вышеперечисленных операций?