import Foundation

func readWords<T>(_ f: (Substring) -> T) -> [T] {
    return readLine()!.split(separator: " ").map(f)
}

let MOD = 1_000_000_009

private func pow(_ b: Int, _ n: Int, _ p: Int) -> Int {
    var (b, n) = (b, n)
    var x = 1
    while n > 0 {
        if n % 2 == 0 {
            b = b * b % p
            n /= 2
        } else {
            x = x * b % p
            n -= 1
        }
    }
    return x % p
}

func main() {
    // 考察過程
    // 対称性、偶奇性
    // A_iが0になるのは、nが奇数のとき。
    // nが奇数なら全てが偶数? 0は一つだけ。他は二つずつ。
    // nが偶数なら全てが奇数。二つずつ。
    // あとは重複あり順列? 人の位置はほぼ固定なので違った。
    // 二通り が n/2(小数点切り捨て)個分。
    // - 🐻 - - - 🐰 -
    // - 🐰 - - - 🐻 -
    // こんな感じ

    let n = Int(readLine()!)!
    let A = readWords { Int($0)! }.sorted()

    if n % 2 == 0 {
        var x = 1
        var count = 0
        for i in 0..<n {
            if A[i] == x {
                count += 1
                if count == 2 {
                    x += 2
                    count = 0
                }
            } else {
                print(0)
                return
            }
        }
    } else {
        var x = 0
        var count = 0
        for i in 0..<n { 
            if A[i] == x {
                count += 1
                if x == 0 && count == 1 || count == 2 {
                    x += 2
                    count = 0
                }
            } else {
                print(0)
                return
            }
        }
    }

    
    print(pow(2, n/2, MOD) % MOD)
}


main()