Using C++ Write a program that implements the Extended Euclidean algorithm to find the greatest common divisor. The program should output the gcd(greatest common divisor) and x and y. Input should be two non-negative integers a and b, with a greater than or equal to b. Your program should also provide an option to calculate the inverse of a number with some modulus(i.e. mod) for the user. Submit a screen shot showing all the working features of your program along with a print out of your code. Here is an example of pseudo-code below for reference of the Extended Euclidean algorithm

INPUT: two non-negative integers a and b with a > b. OUTPUT: d=god(a,b) and integers 2, y satisfying ax + by = d. 1. Ifb=0 then set d a, It-1, y , and return(d,x,y). 2. Set 22+1, 21-0, 42+-0, . 1. 3. While b > 0 do the following: 3.1 qta/b], rta - qb, 2-12 221, yy2 qyi. 3.2 ab, br, 2221, 2+2, 9241, and yiy. 4. Set da, 222, y42, and return(d,x,y)