#!/usr/bin/env python # coding: utf-8 # https://yukicoder.me/problems/no/660 # 提出用に stdin,stdout 仕様にしていますよ。 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: answer += 1 cursor -= 1 yukiko -= i # 限界の半分まできたのにまだ現在地0を超えてなかったら無理。 # or 体力限界。時間よ戻れ。 elif (cursor == n and yukiko <= 1) or 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) # 問題の都合。10^9+7の余りを返却します。 return answer % big_num if __name__ == '__main__': answer = foo(int(stdin.readline())) stdout.write(f'{answer}\n')