package main

import (
	"fmt"
)

const mod = 1e9 + 7

// 这个题用回溯是100%会超时的,必须用增长型map来计算
func countPairs(diliciousness []int) int {
	n := len(diliciousness)
	trace := make([]int, 0, 0)
	var backtrace func(idx int)
	res := 0
	backtrace = func(idx int) {
		if len(trace) == 2 && isValid((trace[0]+trace[1])%mod) {
			fmt.Println(trace)
			res++
		}
		if len(trace) > 2 {
			return
		}
		for i := idx; i < n; i++ {
			trace = append(trace, diliciousness[i])
			backtrace(i + 1)
			trace = trace[:len(trace)-1]
		}
	}
	backtrace(0)
	return res % mod
}

func isValid(num int) bool {
	if num == 0 {
		return false
	}
	return num&(num-1) == 0
}

func main() {
	fmt.Println(countPairs([]int{2160, 1936, 3, 29, 27, 5, 2503, 1593, 2, 0, 16, 0, 3860, 28908, 6, 2, 15, 49, 6246, 1946, 23, 105, 7996, 196, 0, 2, 55, 457, 5, 3, 924, 7268, 16, 48, 4, 0, 12, 116, 2628, 1468}))
}