rt，爆TLE了。题目描述如下

题目描述

从一个无限大的矩阵中心点出发，一步只能向右走、向上走或向左走。恰好走 $N$ 步且不经过已走的点共有多少种走法

输入

一个数字，代表 $N$， $N≤1000$.

输出

输出有多少方案，答案模 $12345$.

输入数据 1

2

输出数据 1

7

蒟蒻代码：

#include <bits/stdc++.h>
#define int long long
#define mod 12345
using namespace std;
bool book[1005][1005];
int n, ans;
void dfs(int x, int y, int t)
{
	if (t == 0) {ans++;ans%=mod;return;}
	else {
		if (book[x + 1][y] == 0) dfs(x+1,y,t-1);
		if (book[x - 1][y] == 0) dfs(x-1,y,t-1);
		if (book[x][y + 1] == 0) dfs(x, y + 1, t - 1);
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
    cout.tie(0);
	book[0][0] = 1;
	cin >> n;
	dfs(0, 0, n);
	cout << ans;
	return 0;
}