In this project, you will implement the dynamic programming-based solution to find the longest common subsequence (LCS) of two sequences. Your inputs will be the two sequences (as Strings) and the outputs are the longest common subsequence (printed as a String) and the final matrix (printed as a two-dimensional array) depicting the length of the longest common subsequences (as shown in the slides) for all possible subsequences of the two input The two input sequences to be used by each student are shown below. The LCS expected for the two sequences is also shown Row Sequence Column Sequence LCS CGGCCAGGCGAT CGAGGTAAGTAG CGAGGGA sal t is shown below Rou Sequec: ATTACCA Submission (through Canvas): Colunn Sequence: ATGCGGGG A word document containing the following: O0 0 (i) entire code (ii) the outputs showing the final dynamic programming table (of the lengths of the longest common subsequences of all possible subsequences of the two input strings) and the longest common subsequence iii) the final alignment (determined manually by working out the alignment based on the table printed in ii, and typed in the word document) of the two input strings and the gaps ( that need to be introduced in order to facilitate an alignment that matches with the LCS obtained. 0 1 2 2 222 222 0 1 2 2 2 2 2 2 22 1 2 2 2 2 2 2 2 2 0 1 2 333 3 333 0 1 2 3 3 3 3 3 3 3 0 1 2 3 3 4 4 4 4 4 1 2 3 3 4 4 4 44 0 1 2 3 4 4 4 4 4 5 01 2 3 4 5 5555 91 23 455555 LCS: ATGGC