import java.awt.*;
import java.awt.event.ItemListener;
import java.awt.event.ItemEvent;
import java.awt.event.ActionListener;
import java.awt.event.ActionEvent;
import java.applet.Applet;

class GraphTriangle extends java.applet.Applet
{

        int modulo=2;
        int numbers=18;
        int filter=-1;

        int red = 255;
        int green = 255;
        int blue = 0;
        int color;
        int cm = 200;
        int wart_mod = 0;

        int max1 = 470;
        int x=(int)(max1 / 2);
        int max = 400;
        int y=2;
		int maxmodulo = 150;

        /* table where we'll place next numbers */
        int [][] tab = new int [max+1][max+1];
		int [][][] hist = new int [maxmodulo+1][maxmodulo+1][maxmodulo+1];
		int [] f = new int [max+1];    
       
		public GraphTriangle( int mod, int nnumbers, int nfilter)
		{
				modulo = mod;
				numbers = nnumbers;
				filter = nfilter;
				
				//clear the table hist
				/*if (numbers == 25) {
					
					max = maxmodulo;
					for (int a=0;a<=maxmodulo;a++){
						for (int b=0;b<=maxmodulo;b++){
							for (int c=0;c<=maxmodulo;c++){
								hist[a][b][c] = 0;	
							}	
						}	
					}
				}*/

		}
		

		     
        /* main function which draws triangle */
        public void paint( Graphics g )
        {        

                drawTriangle( g, modulo, filter);
                
        }
               
		/* *** */
        public int power(int base, int exponent, int modulo) {
        	
        	int result = 1;
        	
        	if (base == 0 && exponent != 0) {
        		return 0;	
        	}
        	
       		base = base % modulo;
        	       		
        	for (int i=1; i<=exponent;i++) {
        		
        		if (result == result*base % modulo) { break; }
        		
        		result = result*base % modulo;
        		
        		if (result == 0) break;
        		
        	}
        		
        	return result;
        		
        }
        
        /* *** */
        public int [] exp_cycle(int base, int modulo) {
        	
        	int [] result = new int [3];        	
        	int [] cyc = new int[modulo+1];
        	int cycle=0;        	
        	
        	cyc[0] = 1;
        	
        	if (base == 0) {
        		result[0] = 2;
        		result[1] = 0;
        		result[2] = 0;	
        	}
        	
        	if (base == modulo) {
        		result[0] = 2;
        		result[1] = 0;
        		result[2] = 0;	
        		return result;
        	} 
        	        	
        	for (int i=1; i<=modulo; i++) {

       			cyc[i] = (cyc[i-1]*base) % modulo;        		
        		
        		if (cyc[i] == cyc[i-1]) {
        			result[0] = 2;
        			result[1] = cyc[i];
        			result[2] = cycle;
        			break;
        		}
        		
        		if (i > 2 && cyc[i] == cyc[1]) {        		
        			result[0] = 1;
        			result[1] = cycle;
        			result[2] = 0;
        			break;
        		}
           		cycle++;        		
        	}
        	
        	
        	return result;
        }
        
        /* for 25th recurrence formula  */
        public int f(int n, int k, int modulo) {
        	
        	if (n < k) {
        		return 0;	
        	}
        	if (n == 0 && k == 0) {
        		return 1;	
        	}
        	if (n < 1 || k < 1) {
        		return 0;	
        	}      	
        	
        	if (k == 1 || k == n) {
        		return 1;	
        	}
        	
        	if (k == 2 || k == n-1) {
        		return (n-1) % modulo;
        	}
        	
        	//Check if it was already generated
        	if (k > (n - (int)(n/2))) {
        		return hist[n][n+1-k][modulo] - 1;	
        	}
        	
        	if (hist[n][k][modulo] > 0) {
        		return hist[n][k][modulo] - 1;
        	}
        	        	
        	/* reccurency */     
        	/*    
        	 *  (a % modulo)^[b mod cycle(a w modulo)]
        	 *
        	 */
        	     	
        	int a=0;
        	int b=0;
        	int result=0;        	
        	
        	a = f(n-1,k-1,modulo);
        	
        	int [] info_a = new int [3];
        	info_a = exp_cycle(a,modulo);
        	
        	if (info_a[0] == 1) {
        		//normal cycle
        		b = f(n-1,k,info_a[1]);        			
        	}
        	
        	if (info_a[0] == 2) {
        		//constant
        		result = info_a[1];
        		
        		/* UWAGA! nie ma jeszcze sprawdzania 
        		 * czy wykaldnik przekracza miejsce	
        		 * od ktorego zaczyna sie pojawiac stala
        		 */
        		 
        	} else {
        		
        		result = power(a,b,modulo);

        	}
        	
			a = f(n-1,k,modulo);
        	
        	info_a = exp_cycle(a,modulo);
        	
        	if (info_a[0] == 1) {
        		//normal cycle
        		b = f(n-1,k-1,info_a[1]);        			
        	}
        	
        	if (info_a[0] == 2) {
        		//constant
        		result += info_a[1];
        		       		 
        	} else {
        		
        		result += power(a,b,modulo);
        		
        	}
        	
        	

        	result = result % modulo;
        	
        	//save for posterity
        	hist[n][k][modulo] = result + 1;
        	
       		return result;
        	
        }
        


        void drawTriangle( Graphics g, int mod, int filter)
        {
                
                /* description */
                Font ft = new Font ( "Tahoma", Font.PLAIN, 12 );
                Font ftb = new Font ( "Tahoma", Font.BOLD, 12 );
                
                g.setFont (ft);
                g.drawString ("Triangles for", 30, 20 );

                g.setFont (ftb);
                g.drawString ("Fractal Numbers", 15, 35 );
                
                g.drawLine(15,40,165,40);
        
                g.setFont (ft);
                g.drawString ("Scale of rest:", 15, 60 );
                g.drawString ("Filter - show only certain rest", 15, 110 );
                
                g.drawString ("0", 15, 90 );
                g.drawString (new Integer(mod-1).toString(), 140, 90 );
				
				int [] rr = new int[3];
				
                if (filter > modulo) {
                        max = 0;
                }
                
                if (mod > 6*cm) {
                        cm = 255;
                }
				
				/* Fibonacci numbers */
				f[0] = 0;
                f[1] = 1;
                for (int i=2;i<=max; i++) {
                        
                        f[i] = (f[i-1] + f[i-2]) % mod;

                }

				
				/* main assumptation */
                for (int i=0; i<=max; i++) {
                        tab[i][0] = 0;
                        
                        if (numbers == 4) {
                                tab[i][0] = 1;
                        }
                        if (i == 0) {
                                tab[0][0] = 1;
                        } else {
                                tab[0][i] = 0;
                        }
                        if (numbers == 11)
                        for (int j=0; j<=max; j++) {
                                tab[i][j] = 0;
                        }
                }
                
                if (numbers == 4) {
                        tab[0][0] = 1;
                        
                }
                
                 /* drawing the scale of rest */
                for (int i=0; i<130;i++) {
                
                        color = (int)(6*cm/130*i);
                        int a = (int)((i*mod)/130);
                        
                        color=(int)(((6*cm)/mod) * a);
                        
                        if (color <= cm) {
                                red=cm;
                                green=color;
                                blue=0;
                        }else if (color <= 2*cm) {
                                      red = cm - (color-cm);
                                       green = cm;
                                       blue = 0;
                        }else if (color <= 3*cm) {
                                       red = 0;
                                       green = cm;
                                       blue = (color - 2*cm);
                        }else if (color <= 4*cm) {
                                       red = 0;
                                       green = cm - (color - 3*cm);
                                       blue = cm;
                        }else if (color <= 5*cm) {
                                       red = (color - 4*cm);
                                       green = 0;
                                       blue = cm;
                        }else if (color <= 6*cm) {
                                       red = cm;
                                       green = 0;
                                       blue = cm - (color - 5*cm);
                        }
                           
                        switch (a) {
                                case 0: red=230;green=230;blue=230;
                                        break;
                        }
                                
                        g.setColor(new Color(red,green,blue));
                        g.drawLine(15+i,65,15+i,75);
                        
                }

                
                
                /* main loop */
                for (int n=1; n<=max; n++) {
                        for (int k=1; k<=n; k++) {
                                
                                
                                /* RECCURENCES */                               
                                if (n == k) {
                                        tab[n][k] = 1;
                                } else if (n == 0 || k == 0) {
                                        
                                        tab[n][k] = 0;
                                        
                                } else {
                                        
                                       
				        			if (numbers == 18) {
					        			tab[n][k] = f(n,k,mod) % mod;	
				        			}
				        				        
								}
				
						/* COLOR */
					
						color=(int)(((6*cm)/mod) * tab[n][k]);
						
						if (color <= cm) {
				        		red=cm;
				        		green=color;
				        		blue=0;
						}else if	 (color <= 2*cm) {
				        		red = cm - (color-cm);
				        		green = cm;
				        		blue = 0;
						}else if (color <= 3*cm) {
				        		red = 0;
				        		green = cm;
				        		blue = (color - 2*cm);
						}else if (color <= 4*cm) {
				        		red = 0;
				        		green = cm - (color - 3*cm);
				        		blue = cm;
						}else if (color <= 5*cm) {
				        		red = (color - 4*cm);
				        		green = 0;
				        		blue = cm;
						}else if (color <= 6*cm) {
				        		red = cm;
				        		green = 0;
				        		blue = (color - 5*cm);
						}
						
						
						if (tab[n][k] == 0) { red=230;green=230;blue=230; }
		
						if (filter != -1 && tab[n][k] != filter) {
				        		red=255;
				        		green=255;
				        		blue=255;
						}
						if (filter != -1 && tab[n][k] == filter) {
				        		red = 0;
				        		green = 0;
				        		blue = 0;
						}
						
						if (filter == modulo) {
				        		red = 0;
				        		green = 0;
				        		blue = 0;
						}
						
						g.setColor(new Color(red,green,blue));
					
						/* drawing the point */
						g.drawLine(x+(k-1)+((int)(n / 2)),y,x+(k-1)+((int)(n / 2)),y);
		        	}
		        	x--;
		        	y++;
				}
    
        }
  
};


public class FractalNumber18 extends Applet implements ItemListener, ActionListener
{
        Choice modL, numbersL, filterL;
        Button czyscButton;
        GraphTriangle tablet;
        int modulo=2;
        int numbers=18;
        int filter=-1;
		
        public void init()
        {        
			/* wyswietlanie na ekranie */
		
			tablet = new GraphTriangle(modulo,numbers,filter);
		
			numbersL = new Choice();
			

			numbersL.addItem("18 - a^b + b^a");

			
			
			czyscButton = new Button("Clear");
	
			modL = new Choice();               
			for (int i=2; i<=1530; i++)
		        	modL.addItem( new Integer(i).toString() );
			
			filterL = new Choice();
			filterL.addItem("all");
			for (int i=0; i<=1530; i++)
		        	filterL.addItem( new Integer(i).toString() );
			
			
			setLayout( new BorderLayout() );
					
			Panel sPanel = new Panel();
			sPanel.setLayout( new FlowLayout() );
			sPanel.add( new Label(" Numbers:") );
			sPanel.add( numbersL );
			sPanel.add( new Label(" Modulo:") );
			sPanel.add( modL );
			sPanel.add( new Label(" Filter:") );
			sPanel.add( filterL );
			
			sPanel.add( czyscButton );
			
			add( "South", sPanel );
			add( "Center", tablet );
			numbersL.addItemListener( this );
			modL.addItemListener( this );
			filterL.addItemListener( this );
			czyscButton.addActionListener( this );
	
       	}
        

        public void itemStateChanged( ItemEvent evt )
        {        
		
			if ( evt.getSource() == modL )
			{
		        String s = evt.getItem().toString();
		        modulo = Integer.parseInt( s );
			}
			if ( evt.getSource() == numbersL )
			{
		        String s = evt.getItem().toString();
		        numbers = Integer.parseInt(s.substring(0,2));
			}
			if ( evt.getSource() == filterL )
			{
		        String s = evt.getItem().toString();
		        if (s.length() >= 3 && s.substring(0,3) == "all") {
					filter = -1;
		        } else {
					filter = Integer.parseInt( s );		        
				}
			
			}
		
			remove( tablet );
			tablet = new GraphTriangle(modulo,numbers,filter);
			add( "Center", tablet );
			validate();
		
        }

	public void actionPerformed( ActionEvent evt )
        {
			remove( tablet );
			tablet = new GraphTriangle(2,1,-2);
			add( "Center", tablet );
			validate();
        }

}