Rik, the Space Traveler

মিঃ রিক একজন বিখ্যাত মহাকাশ ভ্রমণকারী। তিনি ভিক্টা নামে একটি ছায়াপথে বাস করেন। এই ছায়াপথে অনেকগুলো গ্রহ আছে। রিক সমস্ত গ্রহ ভ্রমণ করেন না। তিনি কেবলমাত্র 1 থেকে n পর্যন্ত সংখ্যা দেওয়া গ্রহগুলি ভ্রমণ করেন। গ্রহগুলি বাই-ডিরেকশনাল স্পেস টানেলের মাধ্যমে সংযুক্ত রয়েছে। এই স্পেস টানেলের ভাড়া খুবই সস্তা। যদি গ্রহ u এবং গ্রহ v কোনও স্পেস টানেলের মাধ্যমে সংযুক্ত থাকে তবে মাত্র 1 জিকে দিয়ে u থেকে v বা v থেকে u তে ভ্রমণ করা যায় । এখানে, "জিকে" গ্যালাক্সি ভিক্টার মুদ্রার নাম। রিক তার মানিব্যাগে k জিকে রেখে কোনো একটি গ্রহ x থেকে যাত্রা শুরু করেন। তিনি যেকোনো গ্রহে একাধিক বার যেতে পারেন। যখনই তিনি কোনও স্পেস টানেল ব্যবহার করেন, 1 জিকে তার মানিব্যাগ থেকে হ্রাস পায়। যদি তার মানিব্যাগে অর্থের পরিমাণ কোনও গ্রহ y এ 0 gk হয়ে যায় তবে তিনি ভ্রমণ বন্ধ করে দেন। রিক জানেন যে কোনো গ্রহ x থেকে ভ্রমণ শুরু করলে এর জন্য একাধিক গ্রহ y থাকতে পারে, যেখানে যেয়ে ভ্রমণ বন্ধ করতে হবে এবং ভ্রমণের অনেকগুলি উপায় থাকতে পারে । দুটি উপায় আলাদা হয় যদি ভ্রমণ করা গ্রহগুলি পৃথক হয় বা গ্রহগুলির ভ্রমণ ক্রম পৃথক হয় । 1 থেকে n পর্যন্ত সংখ্যাযুক্ত গ্রহগুলোর একটি বিশেষ বৈশিষ্ট্যও রয়েছে। এই গ্রহগুলোর যে কোনও দুটি গ্রহ u এবং v এর জন্য, u থেকে v বা v থেকে u পর্যন্ত ভ্রমণ করা সর্বদা সম্ভব যদি রিকের কাছে পর্যাপ্ত পরিমাণ জিকে থাকে।

এখন, মিঃ রিক একটি গুরুত্বপূর্ণ বিষয় গণনা করার চেষ্টা করছেন। তিনি যদি তার মানিব্যাগে k জিকে নিয়ে কোনও গ্রহ x থেকে যাত্রা শুরু করেন তবে তিনি কত উপায়ে ভ্রমণ করতে পারেন?

উদাহরণস্বরূপ, ধরা যাক, N = 3। সুতরাং, রিক 1 থেকে 3 পর্যন্ত সংখ্যাযুক্ত গ্রহগুলি ভ্রমণ করতে পারবেন। ধরা যাক, গ্রহ 1 এবং গ্রহ 2 একটি স্পেস টানেলের মাধ্যমে সংযুক্ত, গ্রহ 1 এবং গ্রহ 3 অপর একটি স্পেস টানেলের মাধ্যমে সংযুক্ত রয়েছে। এই ক্ষেত্রে, যদি রিক গ্রহ 1 থেকে 3 জিকে দিয়ে ভ্রমণ শুরু করেন, তাহলে ভ্রমণের সর্বমোট 4টি উপায় রয়েছে। উপায়গুলি হল:

                                   1 -> 2 -> 1 -> 3
                                   1 -> 3 -> 1 -> 2
                                   1 -> 2 -> 1 -> 2
                                   1 -> 3 -> 1 -> 3

Input

প্রথম লাইনে দুটি পূর্ণসংখ্যা রয়েছে n এবং m (2 <= n <= 100; 1 <= m <= (n * (n-1)) / 2)। m হল স্পেস টানেলের সংখ্যা।

তারপর, স্পেস টানেলগুলোকে ব্যাখ্যা করে mটি লাইন। i তম রেখায় দুটি স্পেস-বিভক্ত পূর্ণসংখ্যা ui, vi (1 <= ui, vi <= n; ui ≠ vi) রয়েছে- i তম স্পেস টানেল দ্বারা সংযুক্ত গ্রহ দুটি। দুটি গ্রহ u এবং v এর মধ্যে সর্বাধিক 1টি স্পেস টানেল রয়েছে।

পরবর্তী লাইনে একটি পূর্ণসংখ্যা q (1 <= q <= 103) -ক্য়ুয়েরীর সংখ্যা রয়েছে। এরপরের q লাইনের প্রতিটিতে একটি পূর্ণসংখ্যা k (1 <= k <= 10 7 ) থাকে, যা যাত্রা শুরুর আগে রিকের মানিব্যাগে থাকা মুদ্রার পরিমাণ (জিকে)।

10 পয়েন্টের জন্য: 2 <= n <= 5
40 পয়েন্টের জন্য: 2 <= n <= 20
100 পয়েন্টের জন্য: 2 <= n <= 100

Output

প্রতিটি ক্য়ুয়েরীর জন্য, "Query x:" এভাবে একটি লাইনে আউটপুট হিসেবে দেখাবে, যেখানে x হচ্ছে ক্য়ুয়েরী নম্বর। তারপরের nটি লাইনে পরবর্তী নির্দেশনা অনুসারে আউটপুট দেখাবে। i তম লাইনে, রিক তার মানিব্যাগে k জিকে নিয়ে i তম গ্রহ থেকে ভ্রমণ শুরু করলে কত উপায়ে ভ্রমণ করতে পারে, তার সংখ্যা আউটপুট হিসেবে দেখাতে হবে। যেহেতু উপায়ের সংখ্যাটি খুব বড় হতে পারে, তাই উপায়ের সংখ্যাকে 1000000007 দিয়ে ভাগ করলে যে ভাগশেষ থাকে-সেটি আউটপুট হিসেবে দেখাবে।

Sample

Input	Output
3 2 1 2 1 3 2 3 2	Query 1: 4 2 2 Query 2: 2 2 2
Notes: For the first query: Ways for starting from planet 1 are explained in problem statement. If planet 2 is the starting planet, the ways are: 2 -> 1 -> 2 -> 1 2 -> 1 -> 3 -> 1 If planet 3 is the starting planet, the ways are: 3 -> 1 -> 3 -> 1 3 -> 1 -> 2 -> 1

নোট:

প্রথম ক্য়ুয়েরীর জন্য:

গ্রহ 1 থেকে ভ্রমণ শুরু করলে ভ্রমণের উপায়গুলি এই প্রবলেমের বিবৃতিতে ব্যাখ্যা করা হয়েছে।
গ্রহ 2 যদি সূচনা গ্রহ হয় তবে উপায়গুলি হল:

2 -> 1 -> 2 -> 1
2 -> 1 -> 3 -> 1