题号：NC21336
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
给你一个数组R，包含N个元素，求有多少满足条件的序列A使得
0 ≤ A[i] ≤ R[i]
A[0]+A[1]+...+A[N-1]=A[0] or A[1]... or A[N-1]
输出答案对1e9+9取模
输入描述:
第一行输入一个整数N (2 ≤ N ≤ 10)
第二行输入N个整数 R[i] (1 ≤ R[i] ≤ 1e18)
输出描述:
输出一个整数
备注:
子任务1: n <= 3
子任务2: n <= 5
子任务3: 无限制