//记North[m]为第m步向北走的方法数
//上一步走北，下一步3个方向
//else 2个方向
//North[n]就是走了n-1步时再向北一步
//North[n-1]=f[n-2]

//3*North[i-1]+(f[n-1]-North[n-1])*2
//3*North[i-1]+(f[n-1]-f[n-2])*2
//3*f[n-2]-2*f[n-2]+2*f[n-1]
//2*f[n-1]+f[n-2]