Limits 4s, 1.0 GB

আজকে লীনা সাবঅ্যারে এবং পার্টিশন সম্পর্কে শিখেছে। একটি অ্যারে $A$ দেওয়া হলে, $A$ এর সাবঅ্যারে হল অ্যারেটির একটি অংশ যার উপাদান গুলো পাশাপাশি আছে। যেমন, অ্যারে $[1, 2, 3]$ এর কয়েকটি সাবঅ্যারে হল $[1, 2]$, $[2, 3]$, $[1, 2, 3]$, $[2]$ ইত্যাদি। আর একটি অ্যারের পার্টিশন হলো অ্যারেটিকে কয়েকটি সাবঅ্যারেতে ভাগ করা যেন অ্যারেটির প্রত্যেকটি ইন্ডেক্স একটিমাত্র সাবঅ্যারেতেই থাকে। যেমন, $A$ এর $3$ টি পার্টিশন হল $\{ [1, 2], [3] \}, \{[1], [2], [3]\}, \{[1, 2, 3]\}$ (আরো অনেকগুলো পার্টিশন হতে পারত)।

এখন লীনা ভাবছে, একটি অ্যারের কতগুলো পার্টিশন থাকতে পারে। কিন্তু সে বুঝতে পারল যে সবগুলো পার্টিশন তার কাছে গুরুত্বপূর্ণ মনে হয় না। সে সেইসকল পার্টিশনকে গুরুত্বপূর্ণ মনে করে যাদের এই দুইটি বৈশিষ্ট আছেঃ

এখন একটি অ্যারে দেওয়া হলে, লীনা এই অ্যারেটির কয়টি গুরুত্বপূর্ণ পার্টিশন আছে তা জানতে চায়। এবং তোমাকে সেটি নির্ণয় করতে সাহায্য করতে হবে। যেহেতু উত্তরটি অনেক বড় হতে পারে, তাই উত্তর টিকে $10^9+7$ দ্বারা ভাগ করলে ভাগশেষ বলতে হবে।

Input

তোমাকে অনেকগুলো স্বতন্ত্র টেস্টকেস নিয়ে কাজ করতে হবে। প্রথম লাইনে টেস্টকেস সংখ্যা একটি ধনাত্বক পূর্ণসংখ্যা $T$ দেওয়া হবে।

প্রত্যেক টেস্টকেসের শুরুতে একটি লাইনে একটি ধনাত্বক পূর্ণসংখ্যা $n$ দেওয়া হবে, যা হল $A$ এ উপাদান এর সংখ্যা। তারপরের লাইনে $n$ সংখ্যক পূর্ণসংখ্যা $A_1, A_2, \dots, A_n$ দেওয়া হবে, সংখ্যাগুলোর মাঝে স্পেস থাকবে।

Constraints

$1 \leq T \leq 100$
$1 \leq A_i \leq n$, $A$ এর প্রত্যেক উপাদান $A_i$ এর জন্য।

Subtask 1 (15 points)

$1 \leq n \leq 100$
সব টেস্টকেস মিলিয়ে $n$ এর যোগফল $ \leq 1500 $.

Subtask 2 (15 points)

$1 \leq n \leq 500$
সব টেস্টকেস মিলিয়ে $n$ এর যোগফল $ \leq 4500 $.

Subtask 3 (70 points)

$1 \leq n \leq 5000$
সব টেস্টকেস মিলিয়ে $n$ এর যোগফল $ \leq 45000 $.

Output

প্রত্যেক টেস্টকেসের জন্য একটি লাইনে "Case $x$: $y$" আউটপুট দিবে, যেখানে $x$ হল কততম টেস্টকেস সেই সংখ্যা এবং $y$ হল ওই টেস্টকেসের জন্য আউটপুট। বিস্তারিত বোঝার জন্য স্যাম্পল দেখো।

Sample

InputOutput
2
3
1 1 1
4
3 1 2 4
Case 1: 4
Case 2: 5

Explanation

$[1, 1, 1]$ এর যেকোন পার্টিশনই গুরুত্বপূর্ণ।

$[3, 1, 2, 4]$ এর $5$ টি গুরুত্বপূর্ণ পার্টিশন আছেঃ $\{[3, 1, 2, 4]\}, \{[3, 1, 2], [4]\}, \{[3, 1], [2, 4]\}, \{[3, 1], [2], [4]\}, \{[3], [1, 2, 4]\}$.

Submit

Login to submit.

Statistics

50% Solution Ratio
NirjhorEarliest, Jun '20
Yasir_ArafatFastest, 0.8s
nusuBotLightest, 99 MB
Yasir_ArafatShortest, 943B
Toph uses cookies. By continuing you agree to our Cookie Policy.