>>430
例えば、0≦Sn≦2の場合でも、2^m通りあるでしょ。
1個目が1、(2,3)個目〜(2m-2,2m-1)個目が(1,-1) or(-1,1)、最後が1 or -1

両端に区切りのあるランダムウォーク。そんな個数の1次関数になるような問題じゃないよ。