THS

--[[
http://www.ac-web.org/forums/showthread.php?212872-Stuck-on-a-coding-issue
2*nCr(V/2, K+1) where V = 2^N
It's a close enough answer. Regarding the combinations, you can use stirling's approximation or a multiplicative formula - both result in O(ln(n)) time. I'm so glad you answered, good to meet another engineer on this forum.
]]

local N, K = 100000, 2
-- The program below is this, but with modulo 100003:
-- 2*nCr(V/2, K+1) where V = 2^N

local M = 100003 -- modulo
local V = 2; -- vertices mod M or similar
for i = 1, N-2 do V = (V*2)%M end -- this is not working properly .. for obvious reasons and for being tied to what K is

local n = V
local m = K+1

local function pot(x, n)
    if (n == 0) then return 1 end
    if (n%2 == 1) then return (pot(x,n-1)*x)%M end
    local t = pot(x,n//2)
    return (t*t)%M
end

local function inv(x)
    return pot(x, M-2)
end

local t = 1
for i = 1, n do t = (t*i)%M end
for i = 1, m do t = (t*inv(i))%M end
for i = 1, n-m do t = (t*inv(i))%M end

print("Answer:", 2*t)