def is_valid(bit)
sum = 0
bit.chars.map{ |b|
if b == "1" then
sum += 3
return false if sum < 0
else
sum -= 2
return false if sum < 0
end
}
return true
end
def combi(p, m, a)
if m == 0 then
if a[@p-1] == 1 then
bit = sprintf("%0" + @p.to_s + "b", a)
if is_valid(bit) then
@cnt += 1
end
end
elsif m == p then
if a[@p-1] == 1 then
bit = sprintf("%0" + @p.to_s + "b", a | ((1 << m) - 1))
if is_valid(bit) then
@cnt += 1
end
end
else
combi(p-1, m, a)
combi(p-1, m-1, a | (1 << (p - 1)))
end
end
@p = gets.chomp.to_i
@cnt = 0
(0..@p).to_a.permutation(2).each do |p|
sum = p.inject(:+)
next if sum != @p
m = p[0]
n = p[1]
next if m == 0
next if (m * 3) < (n * 2)
if @p == m then
@cnt += 1
next
end
combi(@p, m, 0)
end
puts @cnt
ZGVmIGlzX3ZhbGlkKGJpdCkKICAgIHN1bSA9IDAKICAgIGJpdC5jaGFycy5tYXB7IHxifAogICAgICAgIGlmIGIgPT0gIjEiIHRoZW4KICAgICAgICAgICAgc3VtICs9IDMKICAgICAgICAgICAgcmV0dXJuIGZhbHNlIGlmIHN1bSA8IDAKICAgICAgICBlbHNlCiAgICAgICAgICAgIHN1bSAtPSAyCiAgICAgICAgICAgIHJldHVybiBmYWxzZSBpZiBzdW0gPCAwCiAgICAgICAgZW5kCiAgICB9CiAgICByZXR1cm4gdHJ1ZQplbmQKCmRlZiBjb21iaShwLCBtLCBhKQogICAgaWYgbSA9PSAwIHRoZW4KICAgICAgICBpZiBhW0BwLTFdID09IDEgdGhlbgogICAgICAgICAgICBiaXQgPSBzcHJpbnRmKCIlMCIgKyBAcC50b19zICsgImIiLCBhKQogICAgICAgICAgICBpZiBpc192YWxpZChiaXQpIHRoZW4KICAgICAgICAgICAgICAgIEBjbnQgKz0gMQogICAgICAgICAgICBlbmQKICAgICAgICBlbmQKICAgIGVsc2lmIG0gPT0gcCB0aGVuCiAgICAgICAgaWYgYVtAcC0xXSA9PSAxIHRoZW4KICAgICAgICAgICAgYml0ID0gc3ByaW50ZigiJTAiICsgQHAudG9fcyArICJiIiwgYSB8ICgoMSA8PCBtKSAtIDEpKQogICAgICAgICAgICBpZiBpc192YWxpZChiaXQpIHRoZW4KICAgICAgICAgICAgICAgIEBjbnQgKz0gMQogICAgICAgICAgICBlbmQKICAgICAgICBlbmQKICAgIGVsc2UKICAgICAgICBjb21iaShwLTEsIG0sIGEpCiAgICAgICAgY29tYmkocC0xLCBtLTEsIGEgfCAoMSA8PCAocCAtIDEpKSkKICAgIGVuZAplbmQKCkBwID0gZ2V0cy5jaG9tcC50b19pCkBjbnQgPSAwCgooMC4uQHApLnRvX2EucGVybXV0YXRpb24oMikuZWFjaCBkbyB8cHwKICAgIHN1bSA9IHAuaW5qZWN0KDorKQogICAgbmV4dCBpZiBzdW0gIT0gQHAKICAgIG0gPSBwWzBdCiAgICBuID0gcFsxXQogICAgbmV4dCBpZiBtID09IDAKICAgIG5leHQgaWYgKG0gKiAzKSA8IChuICogMikKICAgIGlmIEBwID09IG0gdGhlbgogICAgICAgIEBjbnQgKz0gMQogICAgICAgIG5leHQKICAgIGVuZAogICAgY29tYmkoQHAsIG0sIDApCmVuZAoKcHV0cyBAY250