package main import ( "bufio" "fmt" "math" "os" "strconv" ) var sc = bufio.NewScanner(os.Stdin) var rdr = bufio.NewReaderSize(os.Stdin, 1000000) func main() { sc.Split(bufio.ScanWords) l := nextInt() count := 0 for _, v := range revEuclid(int(math.Sqrt(float64(l))), 1, 1) { a, b, c := v[0]*v[0]-v[1]*v[1], 2*v[0]*v[1], v[0]*v[0]+v[1]*v[1] if l > 4*(a+b+c) { count++ count %= 1000003 } } fmt.Println(count) } func nextLine() string { sc.Scan() return sc.Text() } func nextInt() int { i, _ := strconv.Atoi(nextLine()) return i } func revEuclid(n, a, b int) [][]int { ret := make([][]int, 0, 2000) var f func(int, int, int) f = func(m, c, d int) { for e := c + d; e <= m; e += d { if (e-d)%2 == 1 { ret = append(ret, []int{e, d}) } f(n, d, e) } } f(n, a, b) return ret }