Tasty Dishes

All submissions for this problem are available.
Chef's restaurant is the most attractive place to have dinner at. To understand why, let's have a look at a way customers do their orders:
There is only one list of N ingredients in the menu. Every ingredient has its beauty value that does not depend on its taste, but on the way it looks, which is expressed as a positive integer. To order a dish, the customer asks Chef to use all the ingredients from L to R (L is strictly less than R). Chef knows that the dish will be tasty and not only beautiful if the sum of its ingredients' beauty values is divisible by K. Chef does not want to use all the ingredients, so he always excludes one of them. Which one?  The least beautiful one! (in other words  which has the minimal beauty value). Now he wonders  how many segments (L,R) are there such that the sum of their beauty values will be divisible by K after excluding the least beautiful ingredient.
Input:
First line of the input consists of two positive integers  N and K. There are N space separated positive integers  beauty values of the ingredients.
Output:
Output should consist of a single integer  the answer for the problem.
Constraints:
1 ≤ N ≤ 2*10^{5} 1 ≤ K ≤ 10^{9} 1 ≤ beauty value ≤ 10^{9}
Example:
Input:
4 2 1 2 3 4
Output:
2
Scoring:
1 ≤ N ≤ 1000, this subtask is worth 21 point.
1 ≤ K ≤ 100, this subtask is worth 39 points.
There are no special constrains for the remaining 40 points.
Test generation details:
Delivery and sorting of ingredients is quite random thing, so all the test cases will look as follows:
N and K are chosen by setter. An integer M is chosen by setter from interval [100..10^9]. Let B[] be the array of beauty values of ingredients. B[i] is chosen uniformly at random from an interval [1..M] for every 1 ≤ i ≤ N. After B[] is generated setter can choose a positive integer R and do B[i] = B[i]*R for every 1 ≤ i ≤ N. It's guaranteed that even after multiplying every B[i] won't exceed 10^9.
Author:  rubanenko 
Tester:  vamsi_kavala 
Editorial  http://discuss.codechef.com/problems/TASTYD 
Tags  Rubanenko, divideandconq, ltime01, medium 
Date Added:  28062013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 