#2718 피보나치 산

1 s   128 MB  

Description

김피보씨는 피보나치 수열을 매우 좋아한다.
 
김피보씨는 자신이 좋아하는 피보나치 수열을 이용해 별사탕으로 탑을 쌓려고 한다.
 
하지만 김피보씨는 돈도 많아 여러분들을 고용해서 탑을 쌓으려고 한다
 
이런 김피보씨를 위해 피보나치 탑을 쌓아주자.(피보나치 수에 관해서는 Hint에 있다.)
 
예를 들어 N = 4 이라면
피보나치 수열은 1,1,2,3 이므로
 
*
*
**
***
와 같이 탑을 쌓을 수 있다.
 
주의해야 할 것은 김피보씨는 55보다 큰 수를 싫어해서 놓아야 하는 별이 56개 이상이면
 
56으로 나눈 나머지 개수만큼 출력한다. 단, 0또한 싫어해서 나머지가 0일 경우에는 1개를 출력한다.

Input

첫 번째 줄에는 탑의 높이  N(1N≤30이 주어 진다.

Output

 
피보나치 수열대로 줄마다 별을 찍어서 출력한다.

Sample Input

Sample Output

4
*
*
**
***

HINT

피보나치 수는 다음과 같이 정의된다.

F0=0, F1=1, Fn+2=Fn+1+Fn