from sys import stdin, stdout def foo(n): # 家に辿り着いたルート数。 answer = 0 # 雪子現在地。 yukiko = 0 # 雪子現在歩数。 cursor = -1 # 雪子体力限界。 limit = n * 2 - 1 # 歩行履歴リスト。 lis = [None for i in range(limit + 1)] # 問題の都合で登場する数値。 big_num = pow(10, 9) + 7 # ノードの考え方で再起するやつ。図なしでなんて説明したらいいかわかんね。 def bar(yukiko, cursor, lis): nonlocal answer for i in [1,-1]: # 1歩移動。 cursor += 1 lis[cursor] = i yukiko += i # 帰宅。記録してから、時間よ戻れ。 if yukiko == n: # 問題の都合。10^9+7になったらリセットします。 answer = 1 if answer==big_num else answer+1 cursor -= 1 yukiko -= i # 体力限界。時間よ戻れ。 elif cursor == limit: cursor -= 1 yukiko -= i # 次の1歩へ。 else: yukiko, cursor, lis = bar(yukiko, cursor, lis) # for が終わったら時間よ戻れ。 yukiko -= lis[cursor] cursor -= 1 return yukiko, cursor, lis bar(yukiko, cursor, lis) return answer if __name__ == '__main__': stdout.write(foo(int(stdin.readline())))