문제
N개의 정수 R[0], R[1], ..., R[N-1]이 주어졌을 때, 다음을 만족하는 A[0], A[1], ..., A[N-1]의 경우의 수가 총 몇가지인지 구하는 프로그램을 작성하라.
● A[i]는 정수다.
● 0≤A[i]≤R[i] (0≤i≤N-1)
● A[0] + A[1] + ... + A[N-1] = A[0] | A[1] | ... | A[N-1]
여기서 '|' 기호는 이진수의 OR 연산을 뜻한다. OR 연산은 두 값의 각 자릿수를 비교해, 둘 중 하나라도 1이 있다면 1을, 아니면 0을 계산한다. 만약 A=5, B=3일 경우의 OR 연산의 결과는 다음과 같다.
A | B = 5 | 3 = 101 | 011 = 0111 = 7
입력
입력은 여러개의 테스트 케이스로 이뤄지며, 첫 줄에 테스트 케이스의 개수 T(1≤T≤10)가 입력된다.
각 테스트 케이스의 첫 줄에는 2이상 10이하의 정수 N이 입력된다.
그 다음 줄에는 R[0], R[1], ..., R[N-1] 이 입력된다. R[i]는 1이상 1018이하의 정수다.
출력
각 테스트 케이스에 대해 위의 조건을 만족하는 경우의 가지수를 1,000,000,009로 나눈 나머지를 출력한다.
예제
4
2
3 5
3
3 3 3
2
1 128
2
150000150000
15
16
194
420352509
출처
번역
로그인해야 코드를 작성할 수 있어요.