# Task
 You are given integer `n` determining set S = {1, 2, ..., n}. Determine if the number of k-element subsets of S is `ODD` or `EVEN` for given integer k.
# Example
 For `n = 3, k = 2`, the result should be `"ODD"`
 In this case, we have 3 2-element subsets of {1, 2, 3}:
 `{1, 2}, {1, 3}, {2, 3}`
 For `n = 2, k = 1`, the result should be `"EVEN"`.
 In this case, we have 2 1-element subsets of {1, 2}:
 `{1}, {2}`
 `Don't bother with naive solution - numbers here are really big.`
# Input/Output
 - `[input]` integer `n`
    `1 <= n <= 10^9`
 - `[input]` integer `k`
    `1 <= k <= n`
 - `[output]` a string
    `"EVEN"` or `"ODD"` depending if the number of k-element subsets of S = {1, 2, ..., n} is ODD or EVEN.
#using lucas's theorem https://en.wikipedia.org/wiki/Lucas%27s_theorem

def to_bin(n):
    k = 0
    while n >= 2**k: k += 1
    s = ""
    for i in range(k - 1, -1, -1):
        if n - 2**i >= 0: 
            s += "1"
            n -= 2**i
        else: s += "0"
    return s

def subsets_parity(n, k):
    s1 = to_bin(n)
    s2 = to_bin(k)
    for i in range(-1, -len(s2) - 1, -1):
        if s1[i] == "0" and s2[i] == "1": return "EVEN"
    return "ODD"
#using lucas's theorem https://en.wikipedia.org/wiki/Lucas%27s_theorem

def to_bin(n):
    k = 0
    while n >= 2**k: k += 1
    s = ""
    for i in range(k - 1, -1, -1):
        if n - 2**i >= 0: 
            s += "1"
            n -= 2**i
        else: s += "0"
    return s

def subsets_parity(n, k):
    s1 = to_bin(n)
    s2 = to_bin(k)
    for i in range(-1, -len(s2) - 1, -1):
        if s1[i] == "0" and s2[i] == "1": return "EVEN"
    return "ODD"