0 1 2   3   4
x 
  1 
		11
    x2 
				111
				x21
				12 
						1111
						x211
						121
						112
						x22

function solution(n) {
    const memo = [1,1]; // 뛰지 않았을 떄, 1칸 뛰었을 때

    while(n>=memo.length){
        memo.push(memo.slice(-2).reduce((a,b) => a+b)%1234567);
    }

    return memo.pop();
}