← Home
For problem statement at 0-999/300-399/380-389/388/problemD.txt this is a correct solution, but verifier at 0-999/300-399/380-389/388/verifierD.go ends with All 104 tests passed can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"os"
)

const MOD int64 = 1000000007

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var k int64
	fmt.Fscan(in, &k)

	const B = 31

	pow2 := make([]int64, B+1)
	pow2[0] = 1
	for i := 1; i <= B; i++ {
		pow2[i] = (pow2[i-1] * 2) % MOD
	}

	tight := make([]int64, B+2)
	loose := make([]int64, B+2)
	tight[0] = 1

	for i := B - 1; i >= 0; i-- {
		nt := make([]int64, B+2)
		nl := make([]int64, B+2)
		bit := (k >> uint(i)) & 1

		for d := 0; d <= B; d++ {
			if loose[d] != 0 {
				same := int64(1)
				if d > 0 {
					same = pow2[d]
				}
				nl[d] = (nl[d] + loose[d]*same) % MOD
				nl[d+1] = (nl[d+1] + loose[d]) % MOD
			}

			if tight[d] != 0 {
				zeroWays := int64(1)
				if d > 0 {
					zeroWays = pow2[d-1]
				}

				if bit == 0 {
					nt[d] = (nt[d] + tight[d]*zeroWays) % MOD
				} else {
					nl[d] = (nl[d] + tight[d]*zeroWays) % MOD
					if d > 0 {
						nt[d] = (nt[d] + tight[d]*pow2[d-1]) % MOD
					}
					nt[d+1] = (nt[d+1] + tight[d]) % MOD
				}
			}
		}

		tight, loose = nt, nl
	}

	var ans int64
	for d := 0; d <= B+1; d++ {
		ans += tight[d] + loose[d]
		ans %= MOD
	}

	fmt.Fprintln(out, ans)
}