给出n个整数 $ m_1, m_2, m_3, ...... m_n $，请根据以下公式计算计算结果后，对10000009取余
$\sum_{i=1}^n(2m_i + 1)$
给出n个整数 $ m_1, m_2, m_3, ...... m_n $，请根据以下公式计算计算结果后，对10000009取余
$\sum_{i=1}^n(2m_i + 1)$
第一行表示测试多少组测试数据 M（M < 100）
后面每一行共（n+1）个整数。第一数字表示该组测试数据的数量 n，后面跟着就是该 n 个数。
输出 M 行，每一行表示根据计算结果。
输入
2 3 10 12 10 2 5 7
输出
67 26