完成溯源工作后，你和你的小伙伴需要坐高铁前往下一个地点。
高铁上共有 n 个座位排成一列，并且在所有座位之前和之后各有一个前门或后门供乘客上车。共有 m 人需要上车找到位置坐下。
m 名乘客从第一名到第 m 名依次上车找到座位坐下。第 i 名乘客坐下后，第 i+1 名乘客才会开始上车。
由于没有试先安排每名乘客的座位，因此由乘客们自由选择座位。每名乘客有一个理想的目标座位（可以存在两个乘客选择同一个目标座位的情况），然后各自独立的选择从前门或后门上车。
上车后，乘客们会各自走到自己理想的目标座位，如果目标座位已经有人坐了，则会继续按原有方向前进（前门上车的向后走，后面上车的向前走），走到第一个空位后坐下。如果走到最后发现还是没有空位，则这名乘客需要掉头重新寻找座位。
求有多少种方案，使得所有乘客都不需要掉头重新寻找座位。两个方案不同，当且仅当存在任意乘客的目标座位不同，或上车时选择的前门或后门不同。