<p>A <strong>good meal</strong> is a meal that contains <strong>exactly two different food items</strong> with a sum of deliciousness equal to a power of two.</p>

<p>You can pick <strong>any</strong> two different foods to make a good meal.</p>

<p>Given an array of integers <code>deliciousness</code> where <code>deliciousness[i]</code> is the deliciousness of the <code>i<sup>​​​​​​th</sup>​​​​</code>​​​​ item of food, return <em>the number of different <strong>good meals</strong> you can make from this list modulo</em> <code>10<sup>9</sup> + 7</code>.</p>

<p>Note that items with different indices are considered different even if they have the same deliciousness value.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> deliciousness = [1,3,5,7,9]
<strong>Output:</strong> 4
<strong>Explanation: </strong>The good meals are (1,3), (1,7), (3,5) and, (7,9).
Their respective sums are 4, 8, 8, and 16, all of which are powers of 2.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> deliciousness = [1,1,1,3,3,3,7]
<strong>Output:</strong> 15
<strong>Explanation: </strong>The good meals are (1,1) with 3 ways, (1,3) with 9 ways, and (1,7) with 3 ways.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= deliciousness.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= deliciousness[i] &lt;= 2<sup>20</sup></code></li>
</ul>

class Solution {
public:

    struct node{
        int k;
        struct node *next[10];
    } Node;

    struct node head;

    void add(int a){
        struct node *p=&head;
        if (a==0){
            if (!p->next[0]){
                p->next[0]=new node();
                p->next[0]->k=0;
            }
            p->next[0]->k++;
            return;
        }
        while(a){
            if (!p->next[a%10]){
                p->next[a%10]=new node();
                p->next[a%10]->k=0;
            }
            p=p->next[a%10];
            a/=10;
        }
        p->k++;
    }

    int check(int a){
        struct node *p=&head;
        if (a<0) return 0;
        if (a==0){
            if (!p->next[0]) return 0;
            return p->next[0]->k;
        }
        while(a){
            if (!p->next[a%10]) return 0;
            p=p->next[a%10];
            a/=10;
        }
        return p->k;
    }

    void dec(int a){
        struct node *p=&head;
        if (a==0){
            p->next[0]->k--;
            return ;
        }
        while(a){
            p=p->next[a%10];
            a/=10;
        }
        p->k--;
    }

    int countPairs(vector<int>& deliciousness) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        for (int i=0;i<10;i++) head.next[i]=0;
        struct node *x;
        int n=deliciousness.size();
        int p[22];
        p[0]=1;
        p[1]=2;
        for (int i=2;i<22;i++) p[i]=2*p[i-1];
        long long ret=0;
        for (int i=0;i<n;i++) add(deliciousness[i]);
        for (int i=0;i<n;i++){
            for (int j=0;j<22;j++){
                int k=check(p[j]-deliciousness[i]);
                if (k){
                    if ((p[j]-deliciousness[i])==deliciousness[i]) k--;
                    if (k>0) ret+=k;
                }
            }
            dec(deliciousness[i]);
        }
        return ret%1000000007;
    }
};
92818