CSE 3100 Systems ProgrammingHomework #2 Due: 09/20/2018For instructions on how to checkout the template code for the assignment and submit solutions using git, seeinstructions in lab0. Remember to pull, add, commit, and push. Do NOT add object file and executablesin your repo.Exercise 1. (50 points) Modular exponentiation. You have implemented the modular exponentiationin HW1 with a loop. In this problem, you will implement a recursive function to compute the modular ex-ponentiation recursively. A template is provided in powerMod-r.c. Your goal is to complete the powerMod()function. You cannot use loops in the function. Again, you can assume that n > 0, e > 0, and m > 1 andall of them are less than 231− 1.The following three cases give you hints on how to recursively compute the modular exponentiationnemod mwhere n, e, and m are integers such that n > 0, e > 0, and m > 1.nemod m =1 if e = 0(n2mod m)e/2mod m if e is even(n2mod m)e/2· n mod m if e is oddThe division in the exponent is integer division. Also, pay attention to the common term in the last twocases and recall that(x · y) mod m = ((x mod m) · (y mod m)) mod mThe behavior of powerMod-r.c is similar to powerMod.c. Below is a sample session.$ ./powerMod-rPlease enter n, e, and m: 123 456 789123 ** 456 mod 789 = 699Exercise 2. (50 points) Consider the sequence of integers defined by a positive integer x0using therecurrencexk=xk−1/2 if xk−1is even3xk−1+ 1 if xk−1is oddFor example, starting with x0= 13, this produces the following sequence:x0= 13x1= 40x2= 20x3= 10x4= 5x5= 16x6= 8x7= 4x8= 2x9= 1. . .1If a value of 1 is reached, then the sequence becomes repetitive (1, 4, 2, 1, . . .). It has been conjectured byCollatz that the sequence reaches 1 for any positive integer x0.1Write a C program that reads from the standard input two positive integers a and b (a ≤ b), and thenprints to the standard output the integer x between a and b (inclusively) that takes the largest number ofsteps to reach 1, along with the number of steps it takes. In case x is not unique, print the smallest one.The expected outputs on some sample input values are listed below:$ ./collatzEnter a and b: 1 100Longest Collatz chain starts at 97 and takes 118 steps$ ./collatzEnter a and b: 100 200Longest Collatz chain starts at 171 and takes 124 steps$ ./collatzEnter a and b: 1 1000000Longest Collatz chain starts at 837799 and takes 524 stepsWrite all of your code on your 3100 virtual machine in the hw2 folder found at the root of your Git repository.The provided Makefile defines rules for compiling your programs with make powerMod-r and make collatz,respectively. Both programs can be compiled with make all or just make, and all object files and executablescan be removed by executing make clean.1For more on Collatz’ conjecture see