Submission #3608877

---

Source Code Expand

n = gets.to_i
m = Math.log2(n+1).ceil
mod = 10**9+7
dp = Array.new(m).map{Array.new(3,0)}
dp[0][0] = dp[0][1] = 1

for i in 1..m-1
    dp[i][0] += dp[i-1][0]
    dp[i][1] += dp[i-1][1]
    dp[i][2] += dp[i-1][2]*3+dp[i-1][1]
    if n[m-i-1] == 0
        dp[i][0] += dp[i-1][1]
    else
        dp[i][1] += dp[i-1][0]
        dp[i][2] += dp[i-1][1]
    end
    for j in 0..2
        dp[i][j] %= mod
    end
end
p dp[m-1].inject(:+)%mod

Submission Info

Judge Result