typedef long long ll; typedef long double ld; #include using namespace std; // #define int long long #include using namespace __gnu_pbds; template using ordered_set = tree, rb_tree_tag, tree_order_statistics_node_update>; // std::cout << *s.find_by_order(1) << std::endl; // 2 signed main() { // これがないと落ちることがある ios_base::sync_with_stdio(false); cin.tie(0); ll l; cin >> l; const ll MOD = 1000003; l /= 4; ll ans = 0; vector hei; for (ll i = 1; i < 100000; i++) { hei.push_back(i * i); } set> s; for (ll i = 1; 4 * i * i <= l; i++) { for (ll j = i + 1; 2 * j * j + 2 * j * i <= l; j++) { ll a, b, c = 0; a = j * j - i * i; b = 2 * j * i; c = j * j + i * i; ll g = gcd(gcd(a, b), c); vector t; t.push_back(a); t.push_back(b); t.push_back(c); sort(t.begin(), t.end()); a = t[0]; b = t[1]; c = t[2]; s.insert({a / g, b / g, c / g}); } // ll le = i + 1; // ll r = 1e9; // cout << le * le - i * i << " " << 2 * le * i << " " << le * le + i * i << endl; // if (2 * le * le + 2 * le * i > l) // break; // while (r - le > 1) // { // ll m = (r + le) / 2; // if (2 * m * m + 2 * m * i <= l) // { // le = m; // } // else // { // r = m; // } // } // ans += max(0ll, le - i); // cout << i << " " << le << " " << ans << endl; } // for (auto e : s) // { // auto [a, b, c] = e; // cout << a << " " << b << " " << c << endl; // } cout << s.size() % MOD << endl; }