Sum of Medians

তোমাকে n টা পূর্ণসংখ্যার একটি অ্যারে দেয়া আছে যেখানে প্রত্যেকটি সংখ্যা আলাদা আলাদা।

তোমাকে ওই অ্যারে থেকে k টি আলাদা সাবসেট এমন ভাবে নিতে হবে যেনো সাবসেট গুলোর মধ্যমার যোগফল সর্বোচ্চ সম্ভব হয়।

একটি সাব সেট আরেকটি সাব সেট থেকে আলাদা বলে গন্য হবে যদি এমন কোনো সংখ্যা থাকে যা একটি সাব সেট এ আছে কিন্তু আরেকটি সাব সেট এ নেই। n সাইজ এর অ্যারে থেকে 2n-1 টি আলাদা সাব সেট নেয়া সম্ভব।

এই প্রশ্নের জন্যে, তোমার সাব সেট এ L টি সংখ্যা থাকলে, ওদের ছোটো থেকে বড় ক্রম অনুসারে সাজালে
মধ্যমা হলো (L+1)/2 তম অবস্থানে যে থাকে।

যেমন ধর তোমার সাব সেট [2,4,1,3] হলে মধ্যমা হবে 2 আর [1,3,4,5,2] হলে হবে 3.

Input

শুরুতে তোমাকে একটা পূর্ণ সংখ্যা T(0 < T ≤ 1000) দেয়া হবে, যা টেস্ট কেস এর সংখ্যার নির্দেশক।

প্রতিটি টেস্ট কেস শুরু হবে দুটি পূর্ণসংখ্যা n(0 < n ≤ 105 ), k(0 < k < min(2n,1018)) দিয়ে, যাদের পরিচয় উপরে দেয়া আছে।

পরবর্তী লাইন এ তোমাকে উপরে উল্লেখিত n টি পূর্ণ সংখ্যা দেয়া হবে।

সবগুলো সংখ্যা -109 এবং 109 এর মধ্যে।

আর এটি নিশ্চিত যে সবগুলো টেস্ট কেস এর n কে যোগ করলে কখনোই 5×105 অতিক্রম করবে না।

Subtask Details :

Subtask 1,10% পয়েন্ট এর জন্যে: n(0 < n ≤ 2 ), k = 2n-1 ) সকল সংখ্যা 0 ও 10 এর মধ্যে, সবগুলো টেস্ট কেস এর n যোগ করলে কখনোই 100 অতিক্রম করবে না..

Subtask 2, 20% পয়েন্ট এর জন্যে: n(0 < n ≤ 16 ), k = 2n-1 ) সকল সংখ্যা 0 ও 104 এর মধ্যে, সবগুলো টেস্ট কেস এর n যোগ করলে কখনোই 105 অতিক্রম করবে না..

Subtask 3, 40% পয়েন্ট এর জন্যে: n(0 < n ≤ 32 ), k < 2n ) সকল সংখ্যা -105 ও 105 এর মধ্যে, সবগুলো টেস্ট কেস এর n যোগ করলে কখনোই 105 অতিক্রম করবে না..

Subtask 4, 100% পয়েন্ট এর জন্যে: Original Constraints.

Output

প্রতিটি টেস্ট কেস এর জন্যে উত্তর একটি লাইন এ প্রিন্ট করো।

উত্তর অনেক বড় হতে পারে, তাই পুরো উত্তর প্রিন্ট না করে উত্তরটিকে 109+7 দিয়ে ভাগ করে ভাগশেষ টা কে প্রিন্ট করো।

Sample

Input	Output
1 6 9 2 1 3 6 5 4	44