给定长度为𝑛的非负整数序列𝑎，问有多少个长度为𝑛的非负整数序列𝑏，
满足：
𝑏𝑖 ≤ 𝑎𝑖
𝑏1 𝑥𝑜𝑟 𝑏2 𝑥𝑜𝑟...𝑥𝑜𝑟 𝑏𝑛 = 𝑎1 𝑥𝑜𝑟 𝑎2 𝑥𝑜𝑟...𝑥𝑜𝑟 𝑎𝑛
答案对1000000009取模
输入描述:
第一行一个正整数𝑛
第二行𝑛个非负整数𝑎𝑖
输出描述:
输出一个数字，表示答案
备注:
对于30%的数据，1 ≤ 𝑛 ≤ 10，𝑎𝑖≤ 103
对于50%的数据，1 ≤ 𝑛 ≤ 20
对于70%的数据，1 ≤ 𝑛 ≤ 40
对于100%的数据，1 ≤ 𝑛 ≤ 105，𝑎𝑖≤ 230