Le but de ce problème est d'afficher un triangle de Sierpinski à l'écran.
Un triangle de Sierpinski est une fractale, c'est à dire un motif se répétant lui-même. Le triangle de Sierpinski est la figure suivante :
##
#

Qui peut être répété ainsi (niveau 2) :
####
# #
##
#

(On a collé deux triangles supplémentaires identiques au premier, un à droite et un en dessous.)

Écrivez un programme affichant à l'écran un triangle de Sierpinski de niveau n.

ENTREE
Sur la première ligne, un unique entier N < 10^5

SORTIE
Le triangle de Sierpinski de niveau N

CONTRAINTES
1s sur un processeur 1GHz
1000Ko

EXEMPLES

Entrée:
3

Sortie:
########
# # # #
##  ##
#   #
####
# #
##
#