No.152 貯金箱の消失
なお問題文
太郎君にはとても大切にしている貯金箱があります。
それは太郎君が$N$歳の誕生日に、プレゼントとしてもらったものでした。
ところがある日突然、大事にしまっておいた貯金箱が無くなってしまいました。
そこで太郎君は得意の黒魔術を使って行方を捜そうと、黒魔術の本を開くとそこには、
「ヒモで以下の図のような魔方陣を描き、中央にロウソクを立てよ。
それぞれの直角三角形はすべて同じ大きさで、辺の長さはすべて正の整数でなければならない。」
と書かれていました。
太郎君はいま長さ$L$のヒモを持っています。
このヒモを自由に切ったり折り曲げたりすることができるとしたとき、
太郎君が作ることができる魔方陣の形状の種類の数を求めてください。
ただし、ある魔方陣をそのまま整数倍したようなものや、
回転や裏返した形状のものは、同一の形状とみなします。
その後、無事に貯金箱の在り処を探し出した直後、太郎君は二郎君の部屋へ突入したようです。
入力
L
ヒモの長さを表す整数 $L\ (1 \leq L \leq 10,000,000 = 10^7)$ が与えられます。
出力
太郎君が作ることができる魔方陣の形状の種類の数を $1000003$ で割った余りを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
165
出力
3
長さ$(3,4,5)$、$(5,12,13)$、$(8,15,17)$の直角三角形で$3$通りの魔方陣を作ることができます。
それぞれ必要なヒモの長さは $48$、$120$、$160$ で、長さ$165$以内に収まります。
サンプル2
入力
8765
出力
152
サンプル3
入力
47
出力
0
長さが足りないので魔方陣を作ることができません。
貯金箱の行方はわからなくなってしまいました。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。